分摊复杂度的证明

Question

如何证明从容量为零的空向量开始，连续向其中添加n个元素，其一个添加操作的分摊复杂度为O(1)

Answer 1

你这个向量是个什么概念，是数学上的，也就是一个数组；还是C++的Vector？
插入元素的时间复杂度取决于你是用的什么容器装的这个向量。
如果是Vector，如果不设置capacity，每次都要析构+构造N个长度的数组，时间复杂度依次为
1,2,3,4,...，N
平均时间复杂度为O((1+N)/2)=O(N)的。
如果用List，插入就是O（1）的时间复杂度。