使用ArrayList解釋攤餘時間的概念？n數組列表的插入運行時間如何爲O（N）。

Question

用一個簡單的問題

我一直在經歷一本書，它說，它達到了極限，如果ArrayList中充滿了需要O（N）的插入時間插入N元素後的ArrayList將翻一番請解釋通過採取一些因素

的ArrayList .Kindly解釋

Answer 1

分期時間深入淺出的解釋：

如果你的操作說萬次，你真的不關心最壞情況或BEST-該操作的情況 - 您關心的是當您重複操作一百萬次時總共需要多少時間。

因此，如果手術一段時間後手術非常緩慢並不重要，只要「偶爾一次」足夠稀少以緩慢緩解。本質上分攤的時間意味着「如果您進行了許多操作，則每次操作的平均時間」。攤銷時間不一定是恆定的;你可以有線性和對數分期時間或其他任何東西。

讓我們以墊子的動態數組爲例，您將重複添加新項目。通常添加一個項目需要一定的時間（即O（1））。但是每次數組滿了時，都會分配兩倍的空間，將數據複製到新的區域，並釋放舊的空間。假設分配和釋放在恆定時間內運行，這個放大過程需要O（n）時間，其中n是數組的當前大小。

因此，每次放大時，所花的時間大約是最後一次放大的兩倍。但是在做之前你還等了兩次！因此每個擴大的成本可以在插入中「分散」。這意味着從長期來看，將m個項目添加到數組所花費的總時間是O（m），所以攤餘時間（即每個插入的時間）是O（1）。