了解摊销时间和为什么数组插入是O（1）

我正在阅读破解编码访谈和大O章，有关于“摊销时间”的解释。 ArrayList需要增长的东西的典型例子在这里使用。 当一个数组需要增长时，插入将花费O(N)时间，假设它需要将N个元素复制到新的数组中。 这可以。

我不明白的是，当数组的容量加倍时，为什么每个插入的分期时间都是O(1)从我所了解的所有内容来看，无论何时插入数组，它总是一个O(N)操作。 摊销时间有何不同？ 我确定文本是正确的，我只是没有注意O(1)摊销时间概念。

---

我正在回答你似乎困惑的问题，而不是你正式提出的问题。

你真正的问题是如何追加可以是O(1)操作。 如果已经为数组的下一个元素分配了空间，那么追加只是更新有多少元素的记录，并复制条目。 这是一个O(1)操作。

如果溢出可用空间，追加只是昂贵的。 然后你必须分配一个更大的区域，移动整个数组，并删除前一个。 这是一个O(n)操作。 但是如果我们每O(1/n)次只做一次，那么平均来说它仍然可以达到O(n * 1/n) = O(1) 。

平均水平是否取决于你的任务。 如果你正在控制重型机械，在单独操作上花费太长时间可能意味着你不能很快回到旋转叶片，这可能是正常的错误。 如果你正在生成一个网页，那么所有重要的是一系列操作所花费的总时间，这将是每个操作的平均时间乘以操作次数。

对于大多数程序员来说，平均值是重要的。

链接地址: http://www.djcxy.com/p/39657.html

上一篇: Understanding Amortized Time and why array inserts are O(1)

下一篇: O Notation