在最坏的情况下，追加元素(在末尾插入)数组可能已满。因此创建了一个新数组，并将 n 个元素从该数组复制到新数组。

我在文献中读到此操作的最坏情况时间复杂度为 O(1)，为什么会这样？不应该是 O(n) 吗？

我读过 this question .但对我来说没有任何意义!

最佳答案

操作本身是 O(n)。

如果您得到每个元素的平均操作，您得到 O(1)，这就是摊销成本。

查看更多信息 http://en.wikipedia.org/wiki/Amortized_analysis

https://stackoverflow.com/questions/22173998/