為何逐操作最壞情況會高估
假設你想界定一個程式多次呼叫某資料結構操作時整體跑多久。偷懶的做法是找出那個操作所能達到的單一最昂貴情況,再乘以呼叫次數。這永遠是個有效的上界——但可能過度悲觀,因為它假裝每次呼叫都同時撞上最壞情況,而這往往不可能。
用具體的話講陷阱在哪。動態陣列的附加通常是 O(1),但偶爾必須複製現有的全部 n 個元素,所以它的單操作最壞情況是 O(n)。把這個 O(n) 最壞情況乘上 n 次附加,你得到 n 次附加的 O(n^2) 界。然而昂貴的複製不可能同時都昂貴:複製 n 個元素只在大約 n 次便宜附加把陣列養大到 n 之後才發生,所以高成本步驟是分散的。誠實地數它們會得到總計 O(n),而非 O(n^2)。逐操作的界整整高估了 n 倍,因為它忽略了一個事實:某操作的高成本逼得接下來許多操作必然便宜。
認出這種高估正是攤還分析的全部動機。每當昂貴操作罕見且必須由許多便宜操作「掙來」時——陣列擴容、二進位計數器加一、伸展樹重整——「逐操作最壞情況」乘以「操作數」的乘積就鬆,有時鬆上很多倍。反方向的誠實提醒:有時逐操作最壞情況確實是緊的(每個操作可獨立地昂貴),那時攤還分析就幫不上忙。在指望攤還有用之前,你必須先確認昂貴操作之間真的彼此牽制。
多重彈出堆疊:單次 Multipop 可彈出 k 個項目,而 k 可大到目前堆疊大小,所以它的逐操作最壞情況是 O(n)。把 O(n) 乘上 m 個操作得到鬆的 O(n*m) 界。但每個項目被推入一次後只能被彈出一次,所以所有彈出加起來的成本不超過所有推入——對 m 個操作誠實的總計是 O(m),而非 O(n*m)。
逐操作最壞情況乘以次數是有效但常常鬆的上界;攤還分析把它收緊。
乘積界永遠不會錯,只是有時鬆。只有當昂貴操作罕見且彼此受限時,攤還分析才值得做;若每個操作能獨立撞上自身最壞情況,簡單的乘積本就是緊的。