c# - 什么是 List.Add 的渐近复杂度？

Question

我发现关于 List.Add() 的渐近复杂度存在很多争议。我怀疑它的来源是最坏的情况that causes underlying array to resize逻辑上是 O(n) 操作。然而，array grows twice in size每次列表空间不足。这使得 n 元素所需的调整大小与 log(n) 成正比。

这是否意味着在一般情况下 Add 操作的渐近复杂度将是 O(n/log(n))？

List.Add() 的真正基准如下。但是，基准测试并不能真正表达此类操作 - 我们可能会在与直线(对数刻度)的任何偏差变得可见之前耗尽内存。

Answer 1

这意味着 amortized complexity List.Add() 的数量可以通过对调整大小操作求和然后乘以添加到列表中的总数量来计算。

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

但请注意，总和是 geometric series ，我们可以做得更好，而不是假设它是(求和)n*log(n):

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

---

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