成本模型：計算基本步驟

為什麼不直接用碼錶計時？

你現在已經知道演算法是什麼，能夠平靜地閱讀虛擬碼，也能分辨決定性問題與最佳化問題。接下來自然的問題是：我們怎麼說某個演算法「比較好」？最直覺的想法是把兩個都跑一遍、用碼錶計時。這個答案很誘人，但對於設計演算法而言幾乎毫無用處。

碼錶量的是：某一支程式、在某一台機器上、跑某一筆輸入、在某一天的時間。換一台筆電、一種語言、一個編譯器，或背景多開了別的程式，數字就變了。更糟的是，一個在極小輸入上吃虧的聰明演算法，在大型輸入上可能贏得非常多，而單一次計時完全沒告訴你成本將如何「增長」。我們想要的是對演算法本身的判斷，而不是硬體的偶然結果。

於是我們用一個思想實驗取代碼錶。我們發明一台理想化的機器，約定哪些操作算作一個工作單位，然後把這些單位「數」成輸入規模 n 的函數。結果是一個與機器無關的成本：一個描述演算法、而非你的筆電的公式。整個領域就是建立在這個公式之上。

RAM 機器與基本步驟

標準的理想化機器是 RAM 模型（隨機存取機器）。想像一個單一處理器，配上一排無限多、各自編號的記憶體格子，每格存一個數字，且無論位址在哪，存取所需時間都相同。處理器會讀取、寫入、做一次算術或比較、跟隨一個分支，或呼叫一個副程式。每一個這樣的基本動作就是一個基本步驟，而我們規定每個基本步驟恰好花費 1 個時間單位。

那麼什麼算作一個步驟？一個安全的判準是：任何操作「常數量」資料、且「不」迴圈的動作。把兩個數相加、比較兩個數、把一個值指派給變數、用索引取陣列元素 A[i]、判斷一個 if 條件、跟隨一個 goto——每個都是一個步驟。整個迴圈「不」是一個步驟；它是各次迭代步驟的總和。一次函式呼叫，呼叫本身算一個步驟，再加上裡面發生的一切。

計算：一個微型範例

計算步驟其實就是仔細的記帳。看一個最基本的任務：掃描一次，在含 n 個數字的陣列 A 中找出最大值。我們一步步走過去，像在紙上一樣把步驟加起來。

best = A[0]                 // 1 step
for i = 1 to n-1:          // loop runs n-1 times
    if A[i] > best:        // 1 compare each pass
        best = A[i]        // 1 assign, sometimes
return best                // 1 step

線性掃描求最大值。迴圈主體是我們必須逐次迭代計算的部分。

設定行 best = A[0] 執行一次：1 個步驟。
迴圈跑 n-1 次。每一次都做比較 A[i] > best：總共 n-1 次比較，所以光是比較就約有 n 個步驟。
指派 best = A[i] 只在我們找到新的最大值時才執行——介於 0 到 n-1 次之間。無論如何，這最多再加 n-1 個步驟。
最後的 return 是 1 個步驟。再加上迴圈本身的計數器遞增與測試，這些每一輪也各算一個。
總計：一個常數，加上一個常數乘上 n。也就是 c1 * n + c2，其中 c1、c2 是某些常數。我們把它總結為 O(n)——線性時間。

注意我們「沒」做的事：我們沒去煩惱比較是否真的和指派一樣貴，也沒去糾結迴圈計數器是不是恰好算一個步驟。這些選擇會改變常數 c1 與 c2，卻永遠不會改變答案的「形狀」——它始終與 n 成正比。這正是這個模型的用意——它讓我們刻意對常數偷懶，卻仍然得到正確的增長規模。

迴圈、巢狀迴圈，以及直接從程式碼讀出時間

計算執行時間大半就是在數迴圈跑了幾次。一個從 1 到 n、每輪做常數量工作的單層迴圈，成本是 Theta(n)。真正會帶來威力的技巧是巢狀迴圈分析：當一個迴圈坐落在另一個迴圈裡面，你要把迭代次數相乘。外層迴圈跑 n 次，每輪內層迴圈跑 n 次，大致做了 n 乘以 n = n^2 個工作單位——也就是 Theta(n^2)。

要小心：不是每個巢狀迴圈都是 n^2。如果內層迴圈在外層各輪中只跑 1、2、3、…、n 次，總和是 sum from i=1 to n of i，等於 n(n+1)/2——仍然是 Theta(n^2)，但帶著二分之一的常數，這個細節會被大O符號藏起來。相對地，一個每次把範圍對半砍的內層迴圈——像二分搜尋裡那一步——只會跑大約 log n 次，這就是為什麼「對半砍」是許多快速演算法背後的祕密。

哪一筆輸入？最壞、最佳與平均

還有一個沒收尾的地方。步驟數常常取決於你餵進的是「哪一筆」規模為 n 的輸入，而不只是 n 本身。在一個串列中搜尋某個值，可能在第一個元素就停下（幸運），也可能掃完全部 n 個（倒楣）。所以「成本作為 n 的函數」還不是單一個數字——它是該規模下所有輸入上的一整個數值範圍。我們用三種觀點來馴服它。

最壞情況是在所有規模為 n 的輸入中步驟最多的——悲觀者的保證，也是我們最常引用的，因為它是一個沒有任何輸入能打破的承諾。最佳情況是步驟最少的，往往是不該倚賴的僥倖。平均情況是規模為 n 的輸入上的平均值，它確實有用，但帶著一個陷阱：它完全取決於你假設的是「哪一種輸入分布」。換一個分布，平均值就變了。下一篇會仔細拆解這三者。

走之前給你兩個誠實的提醒。第一，我們丟掉的那些隱藏常數是真實存在的：大O符號描述的是增長規模，而不是在每個規模下的判決，所以在常數佔主導的小型輸入上，一個 O(n log n) 的方法真的可能輸給 O(n^2) 的方法。漸進分析講的是「大」的 n。第二，計算基本步驟量的是「時間」；同一個 RAM 模型也讓你去數使用的記憶體格子來衡量「空間」，而一個快的演算法不會自動就是一個省記憶體的演算法。兩個量表都要持續開著。