高成本操作可以很少出現
一次二進制遞增可能翻轉很多位:對末尾有多個一的字加一時,須先把它們歸零,再把下一個零設為一。然而由零開始作長序列遞增時,每次操作平均翻轉位數可以很小。攤還成本限制的是每個允許操作序列的總成本;它不是隨機輸入上的期望,也不一定限制每一次操作。
固定一個有 位的計數器,由最低有效位 開始編號,儲存模 的值。遞增會把末尾的一翻成零,再把下一個零翻成一;若原來全為一,則所有 位都翻成零。每次位翻轉計一個成本單位,其餘成本不計。我們先計算從全零初始狀態開始的 次遞增;下方的勢能證明亦涵蓋其他初始狀態。循環溢出規則很重要:溢出會執行,而非被拒絕。
定義 1.2.1
(操作集合的攤還上界)
固定一個數據結構、一組允許的操作和一個成本模型。若對每個由所指定類別的初始狀態出發、含 個允許操作的序列,實際總成本至多為 (其中 只依賴初始狀態),則稱這些操作的攤還成本至多為 。此保證針對最壞序列的整體總成本,不涉及概率;個別操作的成本可以遠高於 。
總計數
命題 1.2.2
(由零開始的確切翻轉總數)
把一個 位模數計數器由零開始,作 次遞增,每次位翻轉計一個成本單位。總成本恰為
且當 時 。
證明
(逐位計算翻轉次數)
從零開始時,包括跨越循環溢出,第 位每 次遞增翻轉一次;對 ,確切總成本滿足
時確切成本為零;嚴格不等式針對 。為證明逐位計數,第 次遞增前,計數器的值為 模 。第 位恰在較低的 位全為一時翻轉,亦即 能被 整除時翻轉; 也包括在內。數出 中符合者便得到下整項。此上界對 一致成立;單次操作仍可耗費 次翻轉。
概念視角代數
翻轉次數作為數論量
當 時, 末尾的 1 的個數等於 末尾的 0 的個數,所以從零開始的第 次遞增恰好翻轉 個位,其中 是 中因子 的指數。求和,並利用 ( 為 的二進制展開中 1 的個數),得
這正是 時的勢能恆等式:界 的鬆弛量恰好是 的二進制中 1 的個數。
勢能法
定義 1.2.3
(勢能與攤還費用)
勢能為每個狀態 指定一個非負數 。對實際成本為 、使狀態由 變為 的操作,其攤還費用定義為
對計數器,取 為值為一的位的數目。
定理 1.2.4
(只含遞增時的勢能上界)
對 位模數計數器,設初始狀態有 個一位,則任意 次遞增的總翻轉成本至多為 。特別地,由零開始時總成本至多為 。
證明
(每次遞增記兩個單位,再消去中間項)
若一次遞增遇到 個末尾一,則 、 改變 ,故 。若全一後循環溢出,則 、勢能改變 ,故 。對任意 次遞增求和並消去中間項:
由零開始時 ,總成本最多為 。與上面的確切總計公式不同,此證明也適用任意初始狀態,但會多出初始勢能的加項。攤還費用是記帳工具:勢能的負變化可支付翻轉,但實際位翻轉並沒有負成本。
證明透視
勢能論證的每個事實用在哪裏
證明有兩個獨立的成分。按末尾一的個數 分情況,是整個證明唯一用到遞增規則的地方:每次遞增把 個一變成零、把一個零變成一,所以成本是 ,而 改變 ,兩者合起來是常數 。循環溢出的情況本質上不同(沒有零被設為一),其費用是 而非 。之後把各次費用相加,只有靠 才能收尾:捨去 一項,等式才變成不等式 。
同一個剖析也顯示論證對其他操作集合在哪裏失效。對 作遞減,成本為 ,而 由 升至 ,費用為 ,不能以常數為界。這裏沒有上述的抵銷:遞減把末尾的零變成一,方向與 所能支付的相反。
四位計數器的八次遞增
例題 1.2.5
(四位計數器的八次遞增)
由最高有效位開始書寫,從 開始。下表只計翻轉:
| 遞增後次數 | 狀態 | 實際翻轉 | 一的數目 |
|---|---|---|---|
| 1 | 0001 | 1 | 1 |
| 2 | 0010 | 2 | 1 |
| 3 | 0011 | 1 | 2 |
| 4 | 0100 | 3 | 1 |
| 5 | 0101 | 1 | 2 |
| 6 | 0110 | 2 | 2 |
| 7 | 0111 | 1 | 3 |
| 8 | 1000 | 4 | 1 |
實際總數為 15。此處每次攤還費用都是 2,因此減去最終勢能後 。也可計算 。第八次單獨成本為四,但操作序列上界仍然成立。
例題 1.2.6
(從非零狀態出發)
取 ,由 開始,故 。三次遞增依次得到 (翻轉 1 次)、(4 次)、(1 次),總成本為 。每次費用都是 ,所以求和等式為 ,因為 有兩個一。上界 成立且有餘裕。由零開始的公式在這裏不適用:它會給出 。
例題 1.2.7
(經過循環溢出)
取 ,由 開始,故 。三次遞增依次得到 (翻轉 1 次,)、(3 次,)、(1 次,)。實際總成本為 ,各次費用之和為 ,而 。這是費用為 而非 的邊界情況:全一字是唯一一個遞增時不會把任何零設為一的狀態。
操作集合為何重要
證明只涵蓋遞增。模數遞減會把末尾零翻成一,再把下一個一翻成零;全零則循環變成全一。
反例模式
容許遞減會破壞常數上界
一個自然的說法是:即使也容許遞減,每次操作的攤還翻轉成本仍為常數。取 及兩個 位字串 與 。對前者遞增得到後者,翻轉全部 位;對後者遞減得到前者,同樣翻轉全部 位。例如 時這兩個字串是 和 ,每次操作成本為 。因此遞增與遞減交替作 次操作,成本恰為 。
於是,對這個表示及這個混合操作集合,不存在與 無關的攤還上界,無論用哪種記帳方法都一樣,因為在這個序列上上界必須超過每次操作 。修補辦法是把操作集合限制為只含遞增(如上面的定理),或改用另一種表示,並為它另行證明及建立成本模型。
確切公式假設全零初始狀態與指定的模數遞增。若計數器拒絕溢出、動態增長、計入記憶體配置或容許其他操作,規格便不同;其成本須按相應規則分析。
常見錯誤
常見錯誤
(攤還 O(1) 不等於每次操作 O(1))
因為總成本至多為 就斷定每次遞增都很便宜,是錯的。上表中第八次遞增要翻轉四位,一般地單次遞增可以耗費 次翻轉。保證針對的是整個序列的總成本;序列上的平均值低於 ,但個別操作仍可能很貴。
常見錯誤
(忘記初始勢能)
上界 只適用於由零開始。若計數器起初有 個一,正確上界是 。例如由 ()開始,單次遞增成本為 ,超過 ;正確上界是 。若只用 、不加初始勢能,便會錯誤地斷言這次遞增至多花 。
練習
快速檢查
(取 ,由 開始遞增四次。列出每次翻轉成本並核對勢能求和等式。)
逐次記下狀態及一的數目。
解答 · 答案
各狀態為 ,翻轉成本依次為 ,總計 。由起點起一的數目為 ,故各次費用為 、、、。等式為 ,成立。
快速檢查
(若初始狀態為全一,下次模數遞增的實際成本及攤還費用是多少?為何不違反由零開始的總計公式?)
用勢能論證中循環溢出的那一種情況。
解答 · 答案
遞增後變成全零,實際成本為 。勢能由 降至 ,費用為 。這不矛盾:總計公式假設由零開始;由全一狀態出發時,正確上界是 ,而成本 符合此上界。
快速檢查
(取 ,寫出混合操作例子的兩個字串,以及一對遞增—遞減中每次操作的翻轉成本。)
按 與 的形式寫出兩個字串。
解答 · 答案
兩個字串是 與 。對 遞增得 ,翻轉全部 位;對 遞減得 ,同樣翻轉全部 位。因此一對操作共 次翻轉,並回到起點,所以 對(即 次操作)共花 。