List.Add的渐进复杂度是什么？

Question

7

我发现关于 List.Add() 的渐近复杂度存在很多争议。我怀疑其源头是最坏情况导致基础数组重新调整大小，逻辑上应该是 O(n) 操作。然而，每次列表空间不足时，数组的大小会增加两倍。这使得需要为 n 个元素调整大小的次数与 log(n) 成比例。

这是否意味着 Add 操作在平均情况下的渐近复杂度将为 O(n/log(n))？ List.Add() 的真实基准如下。但是，对于这种操作，基准测试并不真正具有代表性 - 在任何偏离直线（在对数刻度上）的变化变得可见之前，我们可能已经耗尽了内存。

- Eugene D. Gubenkov

当数组增长时，确实会移动现有的N/2个元素。这就是你认为它是log N的原因。但新的尚未使用的容量呈指数增长，这抵消了这种影响。第一个元素被移动log N次。最后的N/2个元素移动0或1次。 - usr

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

这意味着可以通过对列表进行调整操作的求和，然后乘以添加到列表中的总数来计算List.Add()的平摊复杂度。其中平摊复杂度是术语。

T(n) = (2 + 4 + 8 + ... + n/2 + n) / n

但请注意，这个求和式是一个等比数列，我们可以比假设它是 (summation) n*log(n) 更好地处理它：

T(n) < 2n/n = 2 -> T(n) is in O(1)

注意：这里我假设您的意思是 add() 作为追加。在任意位置插入元素需要 O(n) 时间，您还需要考虑这一点，这将使最终结果从 O(1) 摊销复杂度变为 O(n) 摊销复杂度。