一個演算法，多種執行時間
在上一篇我們學會了在 RAM 模型中用計算基本步數來衡量成本。但這裡有個一開始幾乎會難倒所有人的驚訝之處：單一個演算法並沒有單一的步數。你餵給它每一個不同的輸入，它就會有一個不同的步數。就算把輸入規模固定在比方說 n = 1000，這個規模下仍有天文數字般多的相異輸入——而演算法可能飛快跑完其中某些，卻在另一些上慢慢爬行。
看一個極小的例子：在一個有 n 個數字的串列中從左到右搜尋某個目標。如果目標就坐在第一格，迴圈比較一次就停了。如果它坐在最後一格、或者根本不在串列裡，迴圈就得把全部 n 格都磨完。同一個演算法、同一個 n——但工作量只取決於你交給它哪個輸入，從 1 步一路到大約 n 步。所以「線性搜尋在大小為 n 的串列上要花幾步？」這個問題並沒有單一答案。我們需要一種方法，把一整族輸入收攏成一個乾淨的結論。
訣竅在於：不再去問單一個輸入，而是一次去問大小為 n 的所有輸入。在這一整族裡，我們可以挑出最貴的那個、最便宜的那個、或者一個典型的那個。這三種選擇正是最壞情況、最佳情況與平均情況。每一種都把雜亂的「逐輸入成本之雲」收斂成一個只跟 n 有關的函數，讓我們之後能拿來在不同演算法之間做比較。
最壞情況：你能信守的承諾
最壞情況執行時間是在大小為 n 的所有輸入上取的步數最大值。把它寫成一個函數 W(n)：對每個 n，看遍該規模下的每一個輸入，取其中最大的成本。對線性搜尋來說，最壞的輸入是目標排在最後、或根本不存在，所以 W(n) 大約是 n 步。這是整門學問裡最重要的視角，原因很簡單：它是一個保證。如果最壞情況是 W(n)，那麼大小為 n 的任何輸入都不可能讓演算法跑得比它更慢。這是個你能對每一位使用者信守的承諾，無論他們的資料有多刁鑽。
正因如此，預設情況下「演算法 X 的執行時間」在沒有特別說明時，指的就是它的最壞情況。它也是對手無法擊敗的那個情況：想像有個對手，能在看過你的程式碼之後才挑選你的輸入，存心要拖慢你。最壞情況正好就是他這場最佳攻擊的代價。對於任何「回應太慢就不可接受」的場合——飛航控制器、支付系統、即時遊戲迴圈——最壞情況才是真正要緊的數字，因為那些便宜的輸入，在昂貴的那一個來臨的當天救不了你。
最佳情況：當作下限有用，當作炫耀危險
最佳情況執行時間 B(n) 是在大小為 n 的所有輸入上取的最小值——也就是在唯一那個最幸運的輸入上的成本。對線性搜尋來說，B(n) 是常數：目標恰好坐在第一格，所以比較一次就停了。最佳情況是最壞情況的自然對照，它也確實帶有誠實的資訊：它告訴你這個演算法不可能比 B(n) 更快，這是它成本的一個貨真價實的下限。
但作為對真實效能的描述，最佳情況在三者之中是最被過度吹捧、也最不可信的。它只由唯一一種幸運的輸入達成，而你幾乎從來無法挑選自己的輸入。一個著名的陷阱：插入排序在已經排好序的陣列上大約只跑 n 步——一個漂亮的線性最佳情況——但在反向排序的陣列上卻要花大約 n^2 步。若把那個 n 的最佳情況當成在描述整個演算法來引用，會嚴重誤導他人。最佳情況作為一個下限是誠實的；但若被拿來當成總結來招搖，它就是個謊言。
平均情況：只在它的假設下才誠實
平均情況執行時間 A(n) 是當輸入隨機抽取時的期望步數——也就是依每個輸入出現的可能性加權後的平均成本。它往往是日常行為最寫實的一張畫像。但它藏著一個承重的假設，你必須把它大聲說出來：隨機，是依照哪一個分布？ 這個平均是在一個假設的輸入機率分布上取的，換掉那個分布，平均也隨之改變。脫離了具體分布，根本不存在所謂「那個」平均情況。
再用線性搜尋把這件事說具體。假設目標一定存在，而且同樣可能落在 n 個位置中的任何一個。那麼若它在第一格就是 1 步、第二格 2 步，依此類推直到 n，平均便是 (1 + 2 + ... + n) / n = (n + 1) / 2，大約 n/2 步。所以在那個均勻假設下，平均是最壞情況的一半。但若在你真實的工作負載中，目標通常靠近前端，真正的平均會小得多；而若它通常根本不存在，平均又會爬回接近 n。這個數字的可信度，完全取決於你為了算出它而假設的那個分布。
當三者分道揚鑣：快速排序的警世故事
對某些演算法來說，三種視角完全一致，日子很好過。比方說合併排序，無論輸入是什麼，它總是乾淨俐落地對半切，做大約 n log n 的工作，所以最佳、平均、最壞情況全都落在 Theta(n log n)。當三種情況一致時，你大可問心無愧地只報一個數字。真正有趣的，是那些三種視角講出截然不同故事的演算法。
普通的快速排序（用固定的樞紐，比方說永遠取最後一個元素）就是經典例子。它的最佳與平均情況是漂亮的 Theta(n log n)，但它的最壞情況——拿到一個已經排好序的陣列——會退化成 Theta(n^2)，因為每一次劃分都只剝下一個元素，遞迴於是變成一條緩慢而失衡的長鏈。所以你引用哪一個情況，徹底改變了結論。只報快速排序的平均，會藏起一道真實存在的 n^2 懸崖，而一個惡意的、或只是運氣不好的輸入，足以把你推下去。
Best / average partition: T(n) = 2 T(n/2) + O(n) -> Theta(n log n) Worst partition: T(n) = T(n-1) + O(n) -> Theta(n^2)
誠實地選擇你的視角
那麼你該報哪一個情況呢？這取決於你需要做出什麼樣的承諾，而一份審慎的分析往往會同時引用不只一個。以下是一套合理的預設處理順序。
- 從最壞情況開始。它是那個保證、那個防對手的數字，也是「執行時間」一詞的預設含義。如果最壞情況已經夠好，你或許不必再往下看。
- 如果最壞情況嚇人卻罕見，就動用平均情況——並說明你的分布。把這裡的「隨機輸入」是什麼意思大聲講清楚，並檢查你真實的工作負載是否真的符合它。一個沒有交代的分布，會讓平均變得毫無意義。
- 把最佳情況當作下限，絕不當作總結。用它來論證「在那個幸運的輸入上沒有人能做得更好」，但絕不要把它當成這個演算法的速度來引用。
- 當差距危險時，與其揭露，不如重新設計。快速排序的 n^2 最壞情況，正是人們為什麼要隨機化樞紐或乾脆換演算法的原因——有時候正確的做法是讓壞情況消失，而不只是把它說出來。
最後一個誠實的提醒，也是糾纏整個成本分析的同一個：就算你選定了某個情況，得出的函數通常仍是用漸進符號來表述的，而漸進符號刻意丟掉了常數與低階項。所以一個 Theta(n^2) 的最壞情況與一個 Theta(n log n) 的最壞情況，描述的是成本如何伸縮，而不是在每個規模上的判決——當 n 夠小時，n^2 的方法仍可能勝出。最壞／最佳／平均這組視角告訴你正在衡量的是哪一個輸入；漸進分析則告訴你那個成本如何成長；唯有兩者結合、並把各自的假設講清楚，才能加總成一個誠實的結論。而這正是下一階要談的主題。