用於堆疊重新定型陣列的攤銷分析

Question

提議。在Stack的調整大小數組實現中，在最壞的情況下，對於任何從 開始的任何操作序列的數組訪問的平均數量是不變的。

證明草圖：對於每一個推（）使所述陣列增長（從大小爲N說 大小2N），考慮N/2 - 1推（）操作，大部分最近引起 堆棧大小增長到k ，對於來自N/2 + 2 to N的k。平均4N陣列訪問到 生長陣列與N/2陣列訪問（每推一個），我們得到每個操作9個陣列訪問的平均成本 。證明任何M操作序列所使用的數組訪問次數與M成比例是更復雜的。 （算法第4版1.4章）

我完全不理解證明素描。請幫助我理解這一點。

Answer 1

我認爲這是一種分期付款分析，您可以在這種分期付款的情況下收取像push（）這樣的請求，而不是直接歸因於他們，因此表明沒有人需要支付太高的賬單，這意味着平均成本做的工作很少。

在這種情況下，當空間用完時，您必須複製整個陣列，但是當您這樣做時會增加兩倍，因此您不會經常複製 - 例如，在大小爲1,2,4,8,16 ......這裏我們將每個數組副本記錄到自上次數組複製以來完成的push（）操作。這意味着如果你除了push（）之外什麼都不做，那麼每個push（）都只能得到賬單，而不是它之後發生的第一個數組拷貝，所以如果bill（分割多個push（）操作） ），那麼攤銷成本很小。

如果在空間用完之前數組的大小爲N，並且大小增加一倍，那麼本文說這需要花費4N操作，這聽起來很合理，而且我們也不關心常數因素。自上次翻番以來，這一切都被分割開來。最後一倍是從N/2到N的大小，因此大約有N/2。這可以讓你將4N操作分割爲N/2個push（）操作，因此每次push操作都會得到一個8的共享帳單。不要忘記push（）涉及一個數組，它是否會觸發一個大小加倍的操作，每次推送9次寫入的平均成本（）。