比較模型（comparison model）

想像你蒙著眼睛排一副撲克牌，唯一能做的事是把兩張牌交給裁判，問「哪張比較大？」。你從來看不到實際的數字；你只知道一連串是非比較的結果。許多著名演算法——插入排序、合併排序、快速排序、二分搜尋、堆積——正是這樣運作：它們只透過比較來接觸資料。比較模型就是這種受限計算方式的規則手冊。

精確地說，在比較模型中，唯一能檢視輸入值的操作是兩個元素之間的比較，回傳 a < b、a = b 或 a > b。演算法可以自由搬動元素，但不能對鍵值做算術、雜湊或讀取它的位元——它取得輸入資訊的唯一管道就是比較的結果。正是這個限制讓乾淨的下界成為可能：既然每一個會學到資訊的步驟都是一次比較，你就能用「比較次數」當作「總工作量」的代用品，而一個必須在許多可能答案之間做區分的演算法，就得問足夠多的是非問題才能把它們分開。

選這個模型的用意，是對「我們到底證了什麼」保持誠實。著名的排序 Omega(n log n) 下界與有序搜尋 Omega(log n) 下界，都是關於這個模型的定理——它們說任何「基於比較」的演算法都無法做得更好。它們並不禁止跳出模型的更快方法：計數排序與基數排序之所以能打破 n log n，正是因為它們偷看了鍵值的數值或位數，而非只做比較。所以比較模型不是自然律；它是一個公平而常見的競技場，之所以被選用，是因為大多數通用的排序與搜尋確實住在裡面，而且它給出的下界恰好與最佳的比較演算法相吻合。