攤還成本（amortized cost）

想像一張一年三百六十元的健身房會員卡。繳費那天，那一次造訪感覺貴得驚人；其餘日子的造訪卻像免費。但若把三百六十元攤到你實際造訪的一百二十次上，每次只花你三元。攤還成本就是把這種「攤開」的想法用在演算法上：我們不問單一最壞操作能有多貴，而問當你把整筆帳攤到一長串操作上時，每個操作平均花多少。

精確地說：對某資料結構執行任意 m 個操作的序列，從空的或固定的初始狀態開始，令 T(m) 為整個序列的實際總工作量。每個操作的攤還成本就是 T(m) 除以 m——真正的總量除以操作數。接著我們找一個對「每一條」序列都成立的界，無論哪個對手挑選這些操作。這仍是最壞情況保證，只是「最壞」針對整條序列，而非單一操作。例如，把 n 個項目附加到動態陣列上總共最多做 O(n) 的工作，即使偶爾的附加會複製整個陣列，所以一次附加的攤還成本是 O(n)/n = O(1)。

攤還成本之所以重要，是因為許多資料結構有罕見的昂貴操作，它們替許多便宜操作買單——而用各自的最壞情況去數每個操作，會大幅高估程式的真實執行時間。關鍵的誠實之處：攤還 O(1) 並不代表每個操作都便宜。當一次附加觸發擴容時，它仍可能花 O(n)；我們只主張這種尖峰夠罕見，使整條序列的平均維持在 O(1)。若你的應用連一次慢操作都無法容忍（例如即時系統），攤還界也許不是你要的東西。