動機
向陣列中插入一個元素通常成本很低,但偶爾陣列已滿,必須把所有現有元素複製到更大的儲存空間。因此,單次插入的最壞情況界可以與目前元素個數成線性關係。若把這個最壞成本攤到每一次插入,就會大大高估一長串操作的成本:昂貴的複製之間隔著許多廉價的操作。
攤銷分析(amortized analysis)先界定整個操作序列的總成本,再把這個界分配給各個操作。它是關於整個序列的最壞情況陳述,而不是對隨機輸入取平均。我們分析一個精確定義的只含插入操作的動態陣列,並以兩個證明得到同一個線性總成本界。
定義
起初陣列為空,容量 。倍增插入的規則如下。
定義 1.12.1
(倍增插入陣列)
設插入前元素個數為 、容量為 。若 ,則把新元素寫入下一個空閒位置。若 ,則配置容量 ,複製全部 個現有元素,然後寫入新元素。成本按每複製一個元素計一個單位,寫入新元素計一個單位。在此模型中,配置儲存空間本身以及釋放舊儲存空間的成本視為零;若採用其他模型,則必須另行計入這些成本。對於由 次插入組成的序列,其實際成本是這些單位之和。
定義 1.12.2
(陣列狀態的勢能)
元素個數為 、容量為 的狀態,其勢能定義為
一次操作的攤銷成本等於其實際成本加上勢能的變化量。勢能是一種記帳用的量,並非實際儲存的計算工作量;它的用處在於其變化量在整個序列上會互相抵銷(telescope)。
定理
定理 1.12.3
(線性總成本)
對每個整數 ,在倍增規則下, 次插入的總成本至多為 。因此攤銷成本每次插入至多為三個單位,儘管單次插入的成本可以是 。
定理 1.12.4
(容量界)
在任意正數 次插入之後,容量滿足 。在初始的空狀態,容量為一。
證明思路或證明
證明
(線性界的勢能證明)
起初 ,且勢能始終非負。若某次插入不需要擴容,則其實際成本為一。 增加一時, 至多改變二,所以其攤銷成本至多為三。
若陣列已滿,則插入前 ,實際成本為 。舊勢能為 。倍增並寫入之後,,,所以新勢能為 。因此攤銷成本為 。對所有操作求和時各項互相抵銷:總實際成本加上最終勢能再減去初始勢能,至多為 。由於最終勢能非負而初始勢能為零,故總實際成本至多為 。
證明透視
為甚麼這個勢能能支付複製
證明有一個設計選擇和三個檢查。選擇是 :它起初為零,每次廉價插入至多上升二,而在陣列已滿時恰好等於 ,與複製成本中的 相同。擴容時這筆已儲存的量被釋放,所以攤銷成本是 ,而不是 。三個檢查分別是:廉價情況(,故費用至多為三)、擴容情況(用到 與 ),以及收尾一步——由 與 ,把抵銷後的恆等式變成不等式 。
同一個剖析也顯示換一種增長規則會在哪裏出問題。若已滿的陣列只由 增至 ,插入後的勢能是 ,所以 ,攤銷成本變成 。擴容時沒有任何量被釋放,勢能無法支付複製;令勢能下降的,正是幾何選擇 。
證明
(容量不變量)
元素個數從不超過容量。在第一次擴容之前,唯一的正元素個數是一,此時容量為一。由 擴容至 之後,新的元素個數是 ,所以新容量嚴格小於新元素個數的兩倍。其後不擴容的插入只會增大元素個數,因而保持這個嚴格不等式。對操作次數作歸納即證得結論。
證明
(同一界的聚合證明)
相繼各次擴容所複製的元素個數依次為 ,最後一次所對應的容量嚴格小於最終的正元素個數 。它們的和小於 ; 次新寫入再加上 。這同樣給出當 時總成本小於 。這個等比級數把每次擴容只計一次,而不是把它的成本攤到每一次操作上。
概念視角代數
以閉式表示的精確總成本
擴容發生在第 次插入,並複製 個元素,其中 滿足 。因此複製成本之和為 ,而 時的精確總成本為
當 時為 。由於 ,總成本小於 ,與定理一致。
例題詳解
例題 1.12.5
(首四次插入)
第一次插入成本為一,之後元素個數/容量為 。第二次複製一個並寫入一個,成本為二,之後為 。第三次複製兩個並寫入一個,成本為三,之後為 。第四次不擴容,只寫入一個,之後為 。總實際成本為 。
例題 1.12.6
(一次成本很高的單一操作)
八次插入之後,容量為八。第九次插入複製八個現有元素並寫入一個,所以其實際成本為九。這並不與定理矛盾:定理界定的是全部九次插入的總和,而不是要求每一次插入的實際成本都至多為三。
例題 1.12.7
(一次勢能計算)
在對容量為四的已滿陣列擴容之前,,。插入之後變為 ,。實際成本為五,而攤銷成本為 。勢能的負變化量抵銷了這一次操作實際成本的一部分。
常見錯誤
反例模式
每次只固定增加一點並不足夠
一個看似合理的說法是:只要規則是「陣列已滿時複製全部元素」,總成本就是線性的。取這樣的規則:陣列已滿時,容量恰好增加一。第二次插入複製一個元素,第三次複製兩個,第 次複製 個。當 時,複製成本為 ,再加上十次寫入的 ,總成本為 ,已超過 。一般地,單是複製就需要 ,所以總成本是平方級的。這個說法之所以不成立,是因為擴容之間的間隔不是幾何增長。修正辦法是加上假設:容量每次乘以固定因子 ,如倍增一樣。
常見錯誤
(攤銷不等於期望)
倍增規則不含任何隨機選擇。在該成本模型下,其線性序列界對每一個插入序列都成立。若把這個界稱為平均情況的結果,就需要一個概率分佈,而定理中並沒有這樣的分佈。
常見錯誤
(攤銷常數成本不等於常數延遲)
這一保證並不表示每次插入都是常數時間:上面的第九次插入成本為九,而在已有 個元素之後的那次插入成本為 。它也不涵蓋刪除、縮小,以及為每個新槽位配置並初始化的成本,除非在新的分析中把這些操作納入。
沿著序列追蹤勢能
記 為第 次插入的實際成本, 為第 次插入之後的勢能,並令 。攤銷成本為 。把前 個等式相加,得
所有中間的勢能都互相抵銷。由於每個 且 ,實際總成本至多為 。證明並不要求勢能在每一步都增加:在擴容時勢能通常反而下降。它所需要的是抵銷恆等式以及對最終勢能的一個下界。
對於首四次插入,每次操作之後的勢能依次為 。變化量為 ,所以攤銷成本為 。它們的和是 ,等於實際總成本 加上最終勢能 。最終儲存的勢能並不是額外的實際收費;它是上界記帳與已完成的工作之間的差額。
以積分作為另一種記帳證明
亦可讓每次插入收取三個積分(credit):一個用於支付它自己的寫入,兩個存起來。當容量由 增長至 時,複製需要 個積分。在先前一次擴容至容量 之後,在該容量再次變滿之前,至少已發生 次插入,其中包括觸發先前那次擴容的插入。它們每一次所存的兩個積分合起來至少提供 個積分。從容量一開始的第一次擴容由第一次插入所存的兩個積分支付。把用不完的積分存起來,可以保持餘額非負。
只有在指明積分從何而來並在每次擴容時驗證餘額之後,這種積分詮釋才構成證明。說一次廉價操作「為以後的操作付費」只是一種直覺;正是對其間插入次數的計數令它變得精確。勢能證明以代數方式編碼了同樣的大致想法,儘管數值勢能不必在每個狀態都等於這一特定積分方案的餘額。
改變增長因子
倍增只是幾何增長的一個例子。設初始容量為一,而且每當陣列已滿時就換成容量 的陣列,其中 為固定整數,複製和寫入的成本不變。所複製的容量依次為 。若最後一次所複製的容量為 ,則它嚴格小於最終的正元素個數 。因此它們的和至多為
再加上 次寫入,得總成本小於 。這個界對所指定的固定整數增長因子有效;對於非整數因子的捨入規則,則需要它們自己的不變量。
幾何增長是以時間換取未使用的容量。由 擴容至 之後,元素個數為 ,所以容量小於元素個數的 倍。在兩次擴容之間,元素個數增加而容量保持不變。因此在任意正數 次插入之後 。較大的 會同時改變複製界與儲存界;最佳的工程選擇可能取決於配置成本、記憶體限制和工作負載,而這些都不屬於此數學模型。
勢能的選擇與有效性
勢能函數並不唯一。所選取的 之所以方便,是因為它在初始空狀態下也非負。不同的函數可以用不同的常數證明同一個總成本界。重要的是:對每一個容許的操作,攤銷成本不等式都成立;初始值已知;並且最終值具有合適的下界。
常見錯誤
(以為勢能必須非負)
不帶最大值的表達式 在初始狀態 下等於 ,因此並非非負。抵銷恆等式真正需要的是 ,而不是 。對 這仍然成立,因為在任意正數次插入之後 (容量界),所以 。若不作這樣的檢查就略去一個為負或未經驗證的最終勢能,便是無效的步驟;在所述的只含插入的模型中,取最大值避免了這種記帳上的麻煩。
攤銷界對所插入的值是穩健的:兩個證明中都沒有出現關於這些值分佈的任何假設。然而它們依賴於模型。若每次複製的成本超過一個常數,或者配置時要初始化每個槽位,就必須把這些成本計入。例如,對每個新配置的槽位收取常數個單位,仍然得到等比和以及線性的總工作量,但常數三不再原封不動地成立。若複製一個元素本身的成本是可變的,則在沒有計入這種可變性的情況下,不得套用單位成本定理。
為甚麼縮小需要單獨的規則
本單元從不移除元素。若加入刪除與縮小操作,容量策略可能出現抖動:在容量已滿時擴容,而一旦佔用量剛好降至一半以下就立即縮小,則交替的插入與刪除會反覆觸發對大陣列的複製。常見的補救辦法是在增長閾值與縮小閾值之間留出間隙,但其正確性與攤銷界需要一個同時針對兩種操作而設計的勢能。上面的只含插入的勢能及證明並不能確立該結果。
空間與時間保證描述的也是不同的資源。容量不等式界定的是每次插入之後所保留的槽位數;攤銷證明界定的是所計入的寫入與複製的總數。一次擴容可能暫時同時需要舊的和新的儲存空間,所以該操作期間的峰值記憶體取決於配置模型。無論是最終容量界還是單位成本的時間證明,單獨都不能確定該峰值。
總結
倍增陣列偶爾會複製所有已儲存的元素,但這些複製發生在呈指數增長的容量處。無論是幾何級數的聚合求和,還是非負勢能,都顯示插入的總成本是線性的。攤銷常數成本與偶爾出現的昂貴單一操作是相容的。
練習
快速檢查
(第五次插入的實際成本和新容量各是多少?)
比較插入前的元素個數與容量。
解答 · 答案
在此之前,元素個數和容量都是四。這次插入複製四個並寫入一個,成本為五;新容量為八。
快速檢查
(在對容量為二的已滿陣列插入元素之前和之後, 分別是多少?)
把 用於倍增前後的狀態。
解答 · 答案
之前,。倍增並插入之後,。
快速檢查
(為甚麼聚合的複製成本級數各項是幾何遞增的?)
看看每次擴容時容量如何變化。
解答 · 答案
每次擴容都令容量加倍,所以所複製的元素個數依次是二的冪。
快速檢查
(該定理是否證明了單次插入具有常數的最壞情況延遲?)
回想例題中的第九次插入。
解答 · 答案
沒有。發生擴容的插入會複製目前所有元素,其實際成本可以是線性的。該定理界定的是整個序列的總和。