动态阵列通过重复加倍的时间复杂度

Question

当我们通过重复加倍实现动态数组时,我们只需创建一个新数组,它是当前数组大小的两倍并复制前面的元素,然后添加新的元素？正确？

所以为了计算复杂度,我们有1 + 2 + 4 + 8 + ....步数？正确？

但

 1 + 2^1 + 2^2 + .... + 2^n  =  (2^(n-1) - 1)  ~  O(2^n). 

但是有人给出了

 1 + 2 + 4 + ... + n/4 + n/2 + n  ~  O(n).

哪一个是正确的？为什么？谢谢

Answer 1

你的总和是在正确的轨道上,但你有太多的条款.:-)

当阵列达到任何2的幂时,阵列的大小将加倍.因此,如果遇到的两个最大功率是2 ^k,那么完成的工作是

2 ⁰ + 2 ¹ + 2 ² + ... + 2 ^k

这是几何系列的总和,它可以用来实现

2 ⁰ + 2 ¹ + 2 ² + ... + 2 ^k = 2 ^{k + 1} - 1 = 2·2 ^k - 1

在你的分析中,你把这个总和写成n个术语,最多2 ⁿ.如果你的数组中有2 ^个n元素,那么这将是正确的总和,但这个指数太多了.相反,由于您的数组中包含n个元素,因此该总和中的最大项为2 ^{lg n}.插入即可

2·2 ^{lg n} - 1 = 2n - 1 =Θ(n)

因此,完成的总工作量为Θ(n),而不是Θ(2 ⁿ).

希望这可以帮助!