關於二元計數器攤銷分析

Question

這是關於二元計數器的攤銷分析。陣列中的所有條目都從0開始，每一步我們都會簡單地遞增計數器。

這裏的作者提到如下。

我們使用的潛在函數等於當前計數中的1位數。

問題1：上面的說法是什麼意思？

和其他問題我已經是在分析中它被提及作爲

N +（N/2）+（π/ 4）+ ---是atmost 2n個。我們如何獲得最高2n的結果？

謝謝！

Answer 1

本例中增加的成本是要執行的位翻轉的數量。

I.e.遞增3（0b11）爲4（0b100）的成本爲3（全部三個位置翻轉）。

現在，你不能說，算法是分期不變的，因爲時間量取決於位翻轉的數量，因此在數量上有所不同。

要解決的一個使用潛在方法上增量操作與0開始的潛在的序列是現在是1

• φ的比特的數量（0）= 0
• φ（1）= 1
• φ（2）= 1
• φ（3）= 2
• φ（4）= 1等

這是有道理的，因爲對於每個爲1的位，未來的增量操作必須在某個點將其更改爲0。因此，無論何時發生增量需要翻轉多於最後一位時，它都會利用該值的潛力。

現在繼續分期分析，你會發現潛在值總是增加1，而在每次增量操作中，你減少了每翻轉1位的可能性。在每次操作中合併這個成本爲2：a）將0轉換爲1，b）爲潛力節省1。在0之前翻轉所有的是支付使用潛力。

參見：http://en.wikipedia.org/wiki/Potential_method

Answer 2

這是一個相當普遍的問題，你可以看到這樣的例子here in PDF解釋在成本方面相當不錯。

從PDF中可以更容易地理解圖形，但它意味着我們可以使用一個單獨的函數，它對應於這種情況下的最小單位，並使其等價於某些顯而易見的值例如，pdf中的1位翻轉功能相當於$ 1。潛在的功能使分析變得簡單。它從0開始，應該是非負的。

Answer 3

只需使用幾何級數，其中a = 1和r = 1/2。幾何級數的總和是

 a(1-r^{n})/(1-r). 

    Here it is (1-(1/2)^{n})/(1-(1/2)) = 2*(1- (1/2)^n). 
As n goes to infinity, it becomes 2.