动态阵列重复倍增的时间复杂度

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 <一口> 0 + 2 <一口> 1> 2>

这是一个几何级数的和，结果是

2 <一口> 0 + 2 <一口> 1> 2> = 2 <一口> k + 1> - 1

在你的分析中，你把这个求和写成有n项，范围到2ⁿ。如果数组中有2ⁿ个元素，这就是正确的和，但这太多了。相反，由于数组中总共有n个元素，因此该和的最大值为2 ^lgn 。插入后得到

2压力;2^{lg n} - 1 = 2n - 1 = Θ(n)

因此，所做的总功是Θ(n)，而不是Θ(2ⁿ)。

希望这对你有帮助!