从列表头部移除所有元素的时间复杂度分析（C#）

这段代码的时间复杂度是O(n²)，既不是O(n)也不是你纠结的O(nⁿ)。

原因如下：

• C#的List<T>底层基于数组实现，调用RemoveAt(0)时，需要把数组里从索引1开始的所有元素整体向前挪动一位来填补头部空位，所以单次RemoveAt(0)的时间复杂度是O(k)，k是当前List的元素数量。
• 当你循环执行100万次移除操作时，总操作次数是1000000 + 999999 + ... + 1，这个求和结果是n(n+1)/2（n为初始元素数），属于O(n²)的时间复杂度量级。

如果只是要清空List，完全没必要这么做，直接调用million.Clear()即可，这个方法的时间复杂度是O(1)——它只是重置了List的Count属性，不会移动任何元素。如果业务上必须逐个从头部移除元素，建议改用LinkedList<T>，它的RemoveFirst()操作是O(1)，总时间复杂度会降到O(n)。

你的代码示例：

List<int> million = new List<int>(1000000);
while (million.Count > 0)
{
     million.RemoveAt(0);
}

内容的提问来源于stack exchange，提问作者niimet