從程式碼直接讀出執行時間

從符號到一種閱讀習慣

本梯級先前的指南建好了詞彙：為何捨棄常數與低階項、作為天花板的大O符號、作為緊界判決的 Theta，以及從常數一路到階乘的成長動物園。這最後一篇指南要把它們花用出去。目標是一種可靠的習慣：你看著一段虛擬碼，數出真正的工作發生的次數是 n 的什麼函數，然後喊出成長——通常一行代數都不必寫。

整套方法立足於第一梯級的一條記帳規則：在 RAM 模型下，每個基本步驟——一次算術運算、一次比較、一次陣列存取——花費的時間是有限的。所以執行時間在常數倍的意義下，就是執行過的基本步驟總數。於是讀出執行時間化約為計數：迴圈體跑了幾次，而每次又做了多少有限的工作？拿到次數，掛上 Theta，就完成了。

兩條規則：循序就相加，巢狀就相乘

幾乎一切都源自加法與乘法規則。加法規則：當兩段程式碼一前一後執行時，它們的成本相加，而一個成長的和會塌縮成較大的那個——Theta(n) 接著 Theta(n^2) 就是 Theta(n^2)，因為較小的項正是我們講好要丟掉的低階塵埃。乘法規則：當一個迴圈巢套在另一個之內時，內層成本每個外層迭代各跑一次，於是成本相乘——一個 n 次迭代的外層迴圈包住一個內層的 Theta(n) 迴圈，便是 Theta(n * n) = Theta(n^2)。

這兩條規則讓你把程式拆成片段、為每片命名、再組裝起來。對一個 n 元素陣列做三個分開的單層迴圈、依序執行？Theta(n) + Theta(n) + Theta(n) = Theta(n)。一個雙層巢狀迴圈緊接在一個單層迴圈之後？Theta(n) + Theta(n^2) = Theta(n^2)。加法規則讓你不會把便宜的初始化程式碼算過頭；乘法規則則是 n^2、n^3 乃至更高次方裡那些指數真正的來處。把這兩條練熟，大多數日常程式碼便會自己讀出來。

當內層範圍會移動：三角形迴圈

巢狀迴圈分析裡最常見的陷阱是三角形迴圈，內層迴圈從外層索引開始而非從零開始。粗略的讀法會說「外層 n、內層 n，所以是 n^2」——它恰好落在正確的類別裡，但理由是錯的，而同樣的草率在別處就會出賣你。誠實的做法是把迭代次數寫成一個總和，再把它算出來。

for i = 1 to n:
    for j = i to n:
        do_constant_work()

# inner runs (n - i + 1) times for each i
# total = sum from i=1 to n of (n - i + 1)
#       = n + (n-1) + ... + 1 = n(n+1)/2

一個三角形迴圈：迴圈體觸發 n(n+1)/2 次，儘管它只有完整 n 乘 n 巢狀的一半左右，仍是 Theta(n^2)。

總和 n(n+1)/2 等於 n^2/2 + n/2。它的主導項是 n^2/2，所以整體是 Theta(n^2)：常數 1/2 與低階的 n/2 正是漸進分析丟掉的部分。這值得內化，因為它解釋了為何那麼多「所有配對」的模式——把每個元素與其後的每個元素比較、填滿表格的上三角——即使各只做了正方形一半的工作，仍是平方級的。n^2 的一半仍是 Theta(n^2)；常數倍永遠不會把你移到較小的類別。

把計數器乘或除的迴圈

並非每個迴圈都對計數器加一。當迴圈變數每一輪加倍——i = 1, 2, 4, 8, ... 直到 n——迭代次數不是 n，而是抵達 n 所需的加倍次數，大約是以 2 為底的 log n。同樣的對數出現在每一輪把範圍減半的迴圈裡，如二分搜尋的減半步驟：大小為 n 的範圍變成 n/2，再變 n/4，約 log n 步後達到大小 1。每當計數器是被一個常數倍縮放、而非被一個常數平移時，就該想到對數。

現在把這個與乘法規則結合，你就能讀出那些著名的形狀。一個跑 n 次的外層迴圈，每一輪做一次二分搜尋式的 Theta(log n) 探測，便是 Theta(n) * Theta(log n) = Theta(n log n)——好的排序所棲身的線性對數類別。一個外層跑 n 次、內層加倍的迴圈同樣是 Theta(n log n)。而一個加倍迴圈巢套在另一個加倍迴圈之內，則是 Theta(log n) * Theta(log n) = Theta((log n)^2)。指數與對數並不神奇；它們不過是把加法與乘法規則套用到計數器在做的事情上而已。

四步驟的閱讀流程

把一切串起來的流程如下。它適用於你最先遇到的、以迴圈為主的程式碼；遞迴的程式碼則把它的計數交給一個遞迴關係式，那由分治法梯級處理。每一步都要帶著兩個警告：先決定你分析的是哪個輸入——通常是最壞情況，因為那才是保證——並確認迴圈體內的工作真的是有限的，因為藏在迴圈裡的一次排序或一次字串複製，會悄悄地把成本乘上去。

找出最內層真正的工作，並確認執行它一次只花費有限的基本步驟數（沒有隱藏的內層迴圈、排序或複製）。
把那份工作執行的次數算成 n 的函數——對計數器做加法（線性）、做縮放（對數），或當內層範圍取決於外層索引時寫成一個總和。
用兩條規則組合各片段：循序的程式碼成本相加（只保留最大項），巢狀迴圈成本相乘。
為得到的成長命名並放進階層中；若上界與下界的計數相遇，就陳述一個 Theta，否則誠實地分別回報 O 與 Omega。

拿一個實例來跑。要在 n 個點中以檢查每一對的方式找出最近的一對，外層迴圈固定一個點（n 種選擇），內層迴圈掃描其後的點（一個三角形範圍），得到 n(n+1)/2 次距離計算，每次是有限的幾次乘法加一次比較。迴圈體有限，計數是 Theta(n^2)，沒有任何循序的程式碼壓過它，所以這個暴力法是 Theta(n^2)。注意我們從未計時——我們直接從結構讀出了類別。

這份閱讀承諾了什麼、又沒承諾什麼

要弄清楚計數描述的是哪個輸入。一個有提前退出的迴圈——在第一個符合處就停下的線性搜尋——最佳情況下跑 Omega(1)，最壞情況下跑 Theta(n)，所以對它套單一個 Theta 是錯的；你要把最壞情況當作保證來回報，或就某個假定的輸入分布分析平均情況並明確標示。平均情況的時間，只有你假定的那個分布有多可信，它就有多可信，所以引用平均值時，絕不要不交代你是對什麼取平均。

也要記得這個類別藏起了什麼。一個 Theta 標籤是關於規模化的陳述，而非每個大小下的判決：它只在 n 越過門檻 n0 之後才管事，所以你丟掉的那些隱藏常數與低階項，能讓一個 Theta(n log n) 的程序在小輸入上真的輸給 Theta(n^2) 的程序。這正是為何正式的排序程序會為極小的子陣列退回插入排序。你剛學到的這份閱讀，告訴你當輸入無限增長時哪個演算法勝出——一件真實且核心的事——但它刻意對交叉點保持沉默，而除非你動手量測，否則你也該如此。