動態數組調整大小的分期分析

Question

調整動態數組大小的問題（作爲ArrayList ADT的一部分）讓我難以置信。

該文本設置了元素添加到數組末尾的場景。當陣列達到其容量時，其尺寸加倍。新的較大數組使用舊數組的元素進行初始化。該過程的分期分析給出了O（n）的複雜性。

那麼下面提出問題：

當容量n中的陣列是滿的，而不是複製N個元素到容量2N的陣列，它們被複制到具有N/4的陣列額外的小區，即容量陣列（N + N/4）。顯示在 上執行n個添加序列，數組仍然以O（n）運行。

任何提示，如何解決這個問題的幫助，非常感謝。我不知道如何處理這樣一個事實，即全容量陣列的尺寸只增加其當前尺寸的一小部分，而不是當前尺寸的倍數。

Answer 1

的連續拷貝具有尺寸N，N（5/4），N（5/4）^ 2，...

因此，K份後，複印的總成本是

sum(i=0,K-1){ N(5/4)^i } 

此時陣列的尺寸爲N(5/4)^(K-1)。

因此，所有剩下的就是證明

O([ sum(i=0,K-1){ N(5/4)^i } ]/[ N(5/4)^(K-1) ]) = O(1) . 

在的話，這是每個數組元素，其攤餘成本複製的總成本。

顯示的公式是真的是非常簡單的，邏輯是一樣一樣的顯示了加倍的相似關係：

O([ sum(i=0,K-1){ N(2)^i } ]/[ N(2)^(K-1) ]) 

我不會帶走你的快樂。