為什麼是 List(T).Clear O(N)？

根據有關該List<T>.Clear方法的 MSDN 文件：

此方法是一個 O(n) 操作，其中 n 是 Count。

為什麼是 O(n)？我問是因為我認為清除 aList<T>可以簡單地通過在T[]內部分配一個新數組來完成。沒有其他類可以引用這個數組，所以我看不出這種方法的危害。

現在，也許這是一個愚蠢的問題……分配一個T[]數組本身是 O(n) 嗎？出於某種原因，我不會這麼認為；但也許是（我現在缺乏電腦科學學位嗎？）。如果是這樣，我想這可以解釋它，因為根據上面引用的相同文件，列表的容量保持不變，這意味著需要構造一個大小相等的數組。

（話又說回來，這似乎不是正確的解釋，因為那時文件應該說“其中 n 是容量” -而不是 Count*）。

我只是懷疑這種方法不是分配一個新數組，而是將目前數組的所有元素清零；我很想知道為什麼會這樣。

*Hans Passant 在對LukeH 的回答的評論中指出，文件是正確的。Clear僅將List<T>;中設置的元素清零 它不需要將所有元素“重新歸零”。

據我所知，目前的實現只是呼叫Array.Clear其內部T[]數組，並且Array.Clear是一個 O(n) 過程。（正如漢斯在評論中指出的那樣，MSDN 文件是正確的，n在這種情況下是列表的Count，而不是它的Capacity。）

但是，即使它只是在T[]內部分配了一個新數組，這仍然是一個 O(n) 過程，因為分配一個大小的數組n涉及將所有元素初始化n為它們的零/空/預設狀態。

當然，沒有什麼可以阻止某種內部詭計，其中數組可以用長度 0 或 42 或其他任何值進行初始化，然後根據需要再次即時自動擴展，從而分攤總體 O(n) 成本。

引用自：https://stackoverflow.com/questions/4798910