攤還分析

存下的存款(stored credit)

當記帳法對便宜操作多收時,那筆額外付款必須存在某處直到用到。存下的存款就是那筆積攢的錢,概念上停在資料結構的特定部位——個別陣列格、堆疊項目、計數器位元、樹節點。它不是程式裡真正的記憶體或變數;它是分析者用來追蹤「哪些未來昂貴工作已預付」的記帳虛構。

存款之所以有用,關鍵在擺放位置。你把存款附到日後處理起來昂貴的那些元素上,這樣當昂貴操作來臨時,所需存款正好就停在工作發生之處。對記帳法下的二進位計數器,你維持不變量「目前每個為 1 的位元都帶 1 單位存款」。把 0 設成 1 花你 2(1 翻轉它,1 當作存款放到那個新的 1 位上);進位時把 1 清成 0 就免費,因為那位元自己的存款付了翻轉費。存款確實位於那些 1 位上,而它們正是未來進位必須清掉的位元。

存下的存款是記帳法操弄的具體對象,而非負規則其實是「沒有元素曾欠下它沒有的存款」。深層的重點是:存下的存款與位勢法包裝成單一數字的量相同——位勢函數不過是把所有元素的存款加總。選擇存款放哪(記帳)與選擇位勢函數(物理學家法)是同一個想法的兩種視角。提醒:存款是證明工具,不是執行時的成本——它不改變程式做的任何事,只改變你如何計算那份工作。

二進位計數器不變量:每個 1 位持有 1 存款。把 0111 加一成 1000:三個 1 位清成 0(每次翻轉由自己的存款支付,免費),第 3 位設成 1(花 2:翻轉加上新存款)。這次加一的攤還成本是 2,與連鎖進位多少無關,因為那些連鎖清除都已預付。

存款停在未來昂貴操作會碰到的元素上;非負規則意味著沒有東西欠的比它持有的多。

存下的存款是想像中的記帳,絕非真正的配置或執行時開銷。它唯一的任務是讓證明走得通——聰明地選它停在哪裡,分析就幾乎變得機械化。

又称
prepaid creditcredit預付存款信用