你一定聽過，在 ArrayList (Java) 或 vector (C++) 這種「動態陣列」的尾巴新增一個元素，它的時間複雜度是 O(1)。但你是否也親身經歷過，當陣列「滿了」的時候，程式會突然「凍結」一下？在那一瞬間，它執行的並不是 O(1)，而是一個昂貴的 O(N) 操作：它必須去申請一個兩倍大的新空間，然後把所有 N 個舊元素一個個搬過去。
這就產生了一個巨大的矛盾：一個操作怎麼可能同時是 O(1) 又同時是 O(N) 呢？這就是「平均」這個詞彙造成混淆的地方。為了解開這個謎團，我們必須釐清兩種截然不同的「平均」：一種是基於「機率」的平均情況分析 (Average-Case Analysis)，另一種則是基於「序列」的攤銷分析 (Amortized Analysis)。
我們將會發現，這兩者之間的分別，就像是「賭徒對下一把牌的期望」和「儲蓄者對年底結餘的保證」之間的根本差異。
平均情況分析 (Average-Case) — 賭徒的幸運期望
「平均情況分析」的核心關鍵字是「機率 (Probability)」。它回答的問題是：「如果我給你成千上萬種隨機的輸入資料，這個演算法平均會跑多快？」這是一種基於「運氣」的外部視角，它假設了所有輸入情況的機率分佈（例如：假設所有輸入都是同等機率的隨機資料）。
最經典的例子就是大名鼎鼎的「快速排序法 (Quicksort)」。我們都知道，快速排序法的「最壞情況」是 O(N^2)。這發生在一個極度倒楣的情況下：例如，當你試圖排序一個「已經排好序」的陣列時，你每次選的「基準點 (Pivot)」都剛好是最小或最大的元素，導致演算法退化成災難性的 O(N^2)。
然而，在「平均情況分析」中，我們假設你拿到的是一手隨機洗勻的牌。在這種情況下，你每次選到的基準點「剛好」是最小或最大的機率非常低。在絕大多數的隨機情況下，你選的基準點都能有效地把資料切成兩半，使得演算法的效能維持在優秀的 O(N log N)。因此，我們說 Quicksort 是一個「平均 O(N log N)」的演算法。但這就像一個賭徒在說：「我 99% 的時間都在贏錢，平均下來我是賺的！」你必須接受，你總是有可能遇到那 1% 的倒楣情況，導致你單次就輸個精光。
攤銷分析 (Amortized) — 儲蓄者的必然保證
「攤銷分析」的核心關鍵字是「序列 (Sequence)」。它與機率、運氣、或輸入資料的隨機性完全無關。它回答的問題是：「如果我連續執行這個操作 N 次，那麼最壞的總成本是多少？把這個總成本攤平到每一次操作上，平均每次操作的成本是多少？」這是一種「內部」的保證，它看的是一個「操作序列」的總體表現。
讓我們回到「動態陣列」的例子。這個資料結構的設計，就像一個有遠見的「儲蓄者」。它知道「搬家」O(N) 是一個昂貴但必然會發生的事件。於是，它在每一次便宜的 O(1)「新增元素」操作時，都像是在「存錢」。假設每次 O(1) 新增操作，我們都多付一點「概念上的費用」存入一個「攤銷戶頭」。例如，我們規定每次新增操作的「攤銷成本」都是 3 塊錢。
假設陣列容量為 8。前 8 次新增操作，每次的「真實成本」都只有 1 塊錢（放入元素）。但我們都付 3 塊錢，於是戶頭裡多存了 8 x 2 = 16 塊錢。當第 9 次新增時，陣列滿了！觸發了 O(N) 事件！「真實成本」暴增：申請 16 個新空間（8 塊錢）+ 搬移 8 個舊元素（8 塊錢）+ 放入 1 個新元素（1 塊錢）= 總共 17 塊錢。但別怕！我們戶頭裡剛好存了 16 塊錢，拿出來支付這個巨大開銷，自己只需要再付 1 塊錢。你看，就連這次最昂貴的操作，它的「攤銷成本」也依然被控制住了。這就是攤銷的魔力：它利用大量的廉價操作，去「預先支付」那個未來必然會發生的昂貴操作。
根本區別：面對「最壞情況」的態度
「平均情況分析」和「攤銷分析」的根本區別，在於它們如何面對「最壞情況」。平均情況分析是基於機率的，它允許「最壞情況」的存在，但它賭你不會遇到它。它告訴你：「你放心，在所有可能的輸入中，只有極少數會觸發 O(N^2)，所以你的『期望值』是 O(N log N)。」這是一種樂觀的期望，但它沒有提供任何單次運行的「保證」。
攤銷分析則是基於序列的，它不關心機率，它直面那個最壞情況。它分析的是一個「最壞的操作序列」，並向你保證：「即使你故意用最壞的方式連續操作我 N 次，我保證你付出的總成本就是 O(N)，因此『攤平』下來，每一步操作的平均成本就是 O(1)。」這不是期望，這是一個承諾。它承認昂貴的 O(N) 操作一定會發生，但它透過結構的巧妙設計（例如兩倍擴容），確保了這個昂貴操作不會太常發生，使得成本可以被完美地「攤銷」掉。
這就是為什麼在設計「即時系統」（Real-time System）時，例如醫院的心跳監測器或飛機的自動駕駛，工程師絕對不敢使用「平均情況」的 Quicksort。因為你不能「賭」那 1% 的最壞情況不會發生。但他們會非常樂意使用「攤銷 O(1)」的動態陣列，因為他們知道，即使發生了最壞的 O(N) 搬移動作，它在總體上的效能也是被保證的，不會因為「運氣不好」而導致整個系統崩潰。
結語：你是在賭博，還是在規劃預算？
現在我們能清楚地回答這個問題了。當你聽到「平均情況 (Average-Case)」時，你應該想到「機率」和「賭博」，它描述的是對一個隨機輸入的效能期望，但它無法保證你「這一次」的運氣。
而當你聽到「攤銷 (Amortized)」時，你應該想到「儲蓄」和「預算」，它描述的是對一個操作序列的效能保證。它告訴你，儘管偶爾會有昂貴的支出，但透過平時的「儲蓄」（廉價操作），這個結構保證你的「平均每筆支出」絕對是低廉的。
理解這兩者的差異，是從「知道」演算法到「洞悉」演算法的關鍵一步。它讓我們學會了如何在「賭一把高效能」和「買一份穩定的保證」之間，做出最明智的工程決策。
