最壞、最好與平均情況（worst-, best- and average-case）

兩筆完全相同大小的輸入，可能讓演算法花天差地遠的工作量，所以單一個數字很少能道盡全貌。想像在一串未排序的清單裡找一個名字：若它剛好排第一，你瞬間就找到；若它排最後或根本不在，你得掃完整串。最壞、最好與平均情況，正是看待這種落差的三種誠實視角——大小為 n 的輸入最慢能多慢、最快能多快，以及在典型輸入上你會預期多少。

把輸入規模固定在 n，看所有這個大小的實例。最壞情況執行時間是這些實例中工作量的最大值——最陰沉的輸入。最好情況是最小值——最走運的輸入。平均情況是平均值，依某個假設的輸入機率分布算出。線性搜尋把這講得很具體：最好情況做 1 次比較（目標排第一），最壞情況做 n 次比較（目標排最後或不存在），而若目標等機率地落在 n 個位置中任一個，平均約是 n/2 次比較。這三者描述的是同一個演算法；它們只是對它問了不同的問題。

實務上以最壞情況為預設，因為它是一個保證：「不論輸入如何，都不會比這更慢」，這正是任何有期限的東西所要的。最好情況多半是個趣聞——它告訴你下限，而非你能指望什麼。平均情況確實有用，卻附帶一個犀利的告誡：它完全取決於假設的輸入分布，若真實輸入不符那個假設，平均值就會誤導。還有一個微妙的表親，隨機演算法的期望時間，那裡的平均是對演算法自己的擲硬幣取的、而非對輸入取的——隨機快速排序這樣算是 O(n log n) 期望，但它的最壞情況仍是 O(n^2)。指明你用的是哪個視角至關重要；光說一句「這是 O(n log n)」是含糊的，除非你說清楚是最壞情況、平均情況，還是期望。