如何证明从容量为零的空向量开始，连续向其中添加n个元素，其一个添加操作的分摊复杂度为O(1)
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
1
376
![ThinkPHP5快速开发企业站点[全程实录]](https://img.php.cn/upload/course/000/000/068/6253d918a3ce7278.png)
收藏
你这个向量是个什么概念，是数学上的，也就是一个数组；还是C++的Vector？
插入元素的时间复杂度取决于你是用的什么容器装的这个向量。
如果是Vector，如果不设置capacity，每次都要析构+构造N个长度的数组，时间复杂度依次为
1,2,3,4,...，N
平均时间复杂度为O((1+N)/2)=O(N)的。
如果用List，插入就是O（1）的时间复杂度。