瞭解已分攤時間和爲什麼數組插入是O（1）

Question

我正在閱讀破解編碼採訪和大O章節，對攤銷時間有解釋。 ArrayList需要增長的東西的典型例子在這裏使用。當數組需要增長時，插入將花費O(N)時間，假設它需要將N個元素複製到新的數組中。這可以。

我不明白的是，當數組容量加倍時，爲什麼每次插入的分期時間是O(1)根據我的理解，無論何時插入數組，它總是一個O(N)操作。攤銷時間有何不同？我敢肯定文本是正確的，我只是不在乎分期付款的時間概念。

Answer 1

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

你真正的問題是如何追加可以是一個O(1)操作。如果已經爲數組的下一個元素分配了空間，那麼追加只是更新有多少元素的記錄，並複製條目。這是一個O(1)操作。

如果溢出可用空間，僅追加代價昂貴。然後你必須分配一個更大的區域，移動整個數組，並刪除前一個。這是一個O(n)操作。但是，如果我們每O(1/n)次只做一次，那麼的平均值爲，但它仍然可以達到O(n * 1/n) = O(1)。

平均值是否取決於您的任務。如果你正在控制重型機械，在單獨操作上花費太長時間可能意味着你不能很快回到旋轉葉片，這可能是正常的錯誤。如果你正在生成一個網頁，那麼所有重要的是一系列操作所花費的總時間，這將是每個操作的平均時間乘以操作次數。

對於大多數程序員來說，平均值是重要的。