同一座階梯上的新問題
你至今爬過的每一階都在問同一個問題：這件事到底做不做得到？一個可判定的語言，是某台圖靈機總能以明確的是或否解決的語言；一個不可判定的語言，例如停機問題，則不論機器跑多久都會擊敗它。那個問題是二元的、與時間無關的——它不在乎機器是眨眼之間就回答，還是過了十億年才回答。從這一階開始，問題變了。我們現在承認某個問題是可解的，並追問那個實際得多的後續：它要花多久？一個總會停機、但在五十個符號的輸入上要花的時間比宇宙年齡還長的判定器，對任何人類目的而言，並不比一個永不停機的好到哪裡去。
所以我們需要一種辦法來衡量機器所做的工作，而最自然的單位早已擺在眼前。圖靈機靠著反覆進行一個微小的動作來計算——讀這一格、寫這一格、移動讀寫頭——一遍又一遍，直到停機。於是我們就乾脆數動作：機器在某個給定輸入上的執行時間，就是它停機前所做的那些步數。這種數步數的做法，是時間複雜度的原料，時間複雜度研究的正是那個數目如何增長。它之所以誠實，是因為它把成本綁在我們早已信任的模型上：沒有掛鐘、沒有硬體，只有讀寫頭的基本動作。
光是步數是個沒用的數字
問題就在這裡：「它花了 4000 步」這句話本身什麼也沒告訴你。排序三個名字要四千步是場大災難；排序一百萬個名字要四千步則是個奇蹟。同一台機器，依它拿到多少輸入，所做的工作量可以天差地遠。所以單一個數字毫無意義。我們真正想要的是一個函數——一條規則，說對於這麼大的輸入，機器最多花這麼多步——好讓我們看出當輸入長大時成本如何擴展。時間複雜度從來不是一個數字；它永遠是輸入大小的函數。
這逼出了一個精確的問題：輸入的大小究竟是什麼？慣例正是你做過的一切早已內建的那一個：輸入是一個字串，它的大小就是它的長度——其中符號的個數——記作 n。一個有五個頂點、七條邊的圖，一個待因數分解的數，一串待排序的清單：每一個都得先寫成某個字母表 Sigma（Σ，符號的集合）上的字串，而 n 就是那個字串有多長。我們以這個 n 來衡量成本。如此一來，時間複雜度就是一個函數 T(n)：機器在任何長度為 n 的輸入上所花的最壞步數。
算哪一種情況？最壞的那一種
即使長度 n 固定，也有許多不同的輸入，而它們未必都花一樣的成本。想想在一串 n 個名字中尋找某個目標。如果你的目標剛好排在第一個，你一步就找到它；如果它在最後，或根本不在，你就得掃完全部 n 個。同樣的 n，兩個截然不同的步數。那我們回報哪一個？這個領域的紀律是回報最壞情況：T(n) 是機器在所有長度為 n 的輸入上所花步數的最大值。我們刻意假設最倒楣的那種輸入。
為什麼要這麼悲觀？有兩個誠實的理由。第一，最壞情況的上界是一種保證：如果機器在最倒楣的輸入上從不超過 T(n) 步，那麼它在任何輸入上都不會超過 T(n)——不論來的是什麼，這個承諾都成立。相較之下，平均情況的數字得仰賴假設輸入抽自某個分布，而真實的輸入很少配合；最壞情況不需要這種假設。第二，一個刻意餵你程式輸入的對手，會專門去找出那個最糟的情況，所以凡是可靠性要緊的地方，最壞情況就是你不得不依循的那個數字。
Linear search for a target in a list of n names input: [ N1 N2 N3 ... Nn ] and a target T step: compare T to N1, then N2, ... stop at the first match BEST case target is N1 -> 1 comparison TYPICAL target somewhere middle -> about n/2 comparisons WORST case target is Nn OR absent -> n comparisons We report the WORST case: T(n) = n comparisons. Same n, three very different costs -- the worst one is the guarantee.
把計數抹平：我們在乎的是增長，不是顆粒
就連一個乾淨的最壞情況 T(n)，也比我們想要的更雜亂。確切的步數取決於一些瑣碎的細節：你的機器有一條紙帶還是兩條，一次比較要花三次還是五次讀寫頭移動，你算不算最後那一趟收尾。把這些全加起來，你在一台機器上可能得到 T(n) = 5n + 17，在另一台上得到 T(n) = 3n + 40——而且還是同一件工作。那些常數與低階項是真實的，但它們是模型與記帳方式的偶然，而非問題本身的偶然。把它們精確釘死，會把我們的答案鎖在某一台特定機器上，而那正是我們不想要的。
出路是只去看當 n 變大時 T(n) 如何增長，忽略常數倍率與低階項。在那個鏡頭下，5n + 17 與 3n + 40 是一樣的：兩者都呈線性增長，像 n 那樣。這正是大 O 記法背後的想法——我們說這兩個演算法都以 O(n) 時間執行，意思是一旦 n 夠大，它們的步數至多就是某個常數乘以 n。大 O 正是緊接著的下一篇的主題，所以這裡我們不把它形式化；現在只要握住那個直覺：它是最壞情況增長率的一個上界，一種說法，意思是「長遠來看這東西像 n（或 n^2，或 2^n）那樣擴展」，同時把那些依機器而定的常數丟掉。
為什麼這套鷹架就是全部重點
這聽起來也許像在清很久的喉嚨——數步數、按長度 n 來衡量、取最壞情況、把常數抹平。但這四個選擇恰恰就是讓我們能在能快速解決與不能解決的問題之間畫出一條有意義界線的東西。一旦 T(n) 是 n 的一個乾淨函數，我們就能把演算法排上一座增長率的階梯：常數、對數、線性、n log n、平方 n^2、立方 n^3，而在階梯遠處則是令人聞之色變的指數 2^n。隔幾階看起來相似；把 n 拉開，鴻溝就大得驚人。在 n = 50 時，一個 n^3 演算法在 125000 步內完成，而一個 2^n 演算法卻需要超過 10^15 步——這是瞬間與永不的差別。
那道鴻溝，正是我們把那條頭條界線畫在多項式增長處的緣由——任何被 n 的某個固定次方界住的 T(n)，像 n、n^2 或 n^100。多項式執行時間是易處理（可有效解決）問題的實用定義，而指數時間則是難處理性的標記。接下來三篇就直接建在你剛搭好的這套機具上：第二篇把大 O、大 Omega 與大 Theta 講精確，並排出增長階梯；第三篇定義 P 類——在確定型機器上可於多項式時間內判定的問題；第四篇說明為何 P 在合理模型之間穩健不變；而第五篇則誠實地問，「多項式」是否真的等於「可行」。
最後一次對齊，能讓這一切與之前的一切保持一致。從頭到尾，我們都以整個學科的同一種方式陳述問題：當作是/否問題，也就是那些答案為「是」的輸入所構成的語言。「這個圖連通嗎？」、「這個數是質數嗎？」、「這串清單排好序了嗎？」——每一個都是一次成員資格測試，而機器的工作就是判定它。衡量那個判定的步數如何隨 n 增長——在最壞情況下、忽略常數——就是這一階梯的全部計畫。後面的一切，不過是替那增長的各個區域命名並加以探索而已。