攤還成本對平均情況成本

兩個概念因都涉及「取平均」而常被混淆：攤還成本與平均情況成本。它們聽來相似，卻立基於完全不同的根基。攤還成本是把工作攤到一串操作上，不對機率做任何假設；平均情況成本是對一個隨機輸入分布取平均，本質上關乎機率。把它們搞混會導致過強或根本無意義的主張。

平均情況分析問：若輸入從某個假定的分布中隨機抽取，期望執行時間是多少？它的答案完全取決於那個假定的分布——換分布平均就變，而最壞情況輸入仍可能慢。例如隨機快速排序，對它自己的硬幣翻轉跑 O(n log n) 的「期望」時間，但它的最壞情況仍是 O(n^2)。攤還分析問的則完全沒有隨機：對手挑選的「最壞可能序列」上，總工作量除以操作數是多少？它「每操作 O(1)」的保證對每一條序列都確定成立——沒有機率分布，也沒有期望。動態陣列的附加是攤還 O(1)，這是關於任何附加序列的鐵一般事實；它不是「在平均輸入上 O(1)」。

實務上的差別在於你買的是什麼保證。攤還界是確定性的承諾：無論如何，序列上的總工作量有界，雖然個別操作可能尖峰。平均情況界是機率性的陳述：典型輸入快，但不走運或對手構造的輸入可能慢。一個微妙的橋樑：當演算法是隨機的，人們有時計算「期望攤還成本」，它結合兩者——既對硬幣翻轉取平均、又對序列取平均——但那是刻意的結合，與單獨任一者不同。誠實的拇指法則：若主張提到分布或期望，那是平均情況；若它界定的是最壞情況序列上的總和且無機率，那是攤還。