.net - 为什么要使用List(T).Clear O(N)？

Question

根据the MSDN documentation on the List<T>.Clear method:

This method is an O(n) operation, where n is Count.

为什么是O(n)？我问是因为我认为清除 List<T>可以简单地通过在内部分配一个新的 T[]数组来完成。没有其他类可以对此数组进行引用，因此我看不到这种方法的危害。

现在，也许这是一个愚蠢的问题...是在分配一个 T[]数组本身O(n)吗？出于某种原因，我本来不会这样认为。但也许是这样(我现在是否缺少大学学位？)。如果是这样，我想可以解释一下，因为根据上面引用的相同文档，列表的容量保持不变，这意味着需要构造大小相等的数组。

(然后，这似乎不是正确的解释，因为文档应该说“n是Capacity”- 而不是 Count *)。

我只是怀疑这种方法而不是分配新的数组，而是将当前元素的所有元素清零。我很好奇为什么会这样。

* Hans Passant在对 LukeH's answer的评论中指出该文档是正确的。 Clear仅将 List<T>中设置的元素清零；它不需要将那些之后的所有元素“重新归零”。

Answer 1

据我所知，当前的实现只是在其内部Array.Clear数组上调用 T[] ，而Array.Clear是一个O(n)进程。 (正如汉斯在评论中指出的那样，MSDN文档是正确的，在这种情况下，n是列表的 Count ，而不是列表的 Capacity 。)

但是，即使它只是在内部分配了一个新的T[]数组，这仍然是一个O(n)进程，因为分配大小为n的数组涉及将所有n元素初始化为它们的零/空/默认状态。

当然，没有什么可阻止某种内部欺骗的方法，在该方法中，可以使用长度0或42或任何长度初始化数组，然后根据需要即时自动扩展，从而分摊总体O(n)成本。