动态数组通过重复加倍的时间复杂度

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).

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

- Dubby

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ⁿ。如果你的数组有2的n次方个元素，那么这将是正确的求和，但这个数字增长得太快了。而实际上，由于数组中共有n个元素，因此这个求和的最大项应该是2的lg n次方。将其代入式中可得

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

因此，总的工作量为Θ(n)，而不是Θ(2ⁿ)。

希望这能帮到你！

- templatetypedef

---

你可以解释一下为什么使用紧界Θ而不是O吗？ - Dubby

由于实际限制为2n-1，我们知道这项工作是线性函数，并且可以用theta来界定它，而不是O。 - templatetypedef