無懼地讀懂虛擬碼

虛擬碼是什麼、不是什麼

你已經從前一篇學到，演算法是一份有限、明確的食譜，能把每個合法輸入變成正確的輸出。虛擬碼就是我們把這份食譜寫下來、讓人讀懂的方式。它不是 Python、不是 C，也不是任何一種特定語言——它借用程式設計有用的骨架（賦值、迴圈、if 判斷、函式呼叫），丟掉那些會讓人分心、與想法無關的瑣碎部分（分號、型別宣告、import 敘述）。

這份自由正是重點所在。因為讀虛擬碼看的是意義而非語法，同一個迴圈在一本書裡寫 `for i = 1 to n`，在另一本裡寫 `for each i in [1..n]`，兩者意思完全相同。你的任務從來不是去編譯它，而是去理解它在算什麼。這正是問題、演算法與程式之間劃下的那條線：虛擬碼活在演算法層次——也就是想法——而不是程式層次，後者只是那個想法的一種具體可執行編碼。

每段虛擬碼都由這五樣東西組成

你這輩子會遇到的虛擬碼，幾乎都只由五種動作搭起來，一旦你能叫出它們的名字，恐懼就消失了。第一是順序：先做這個，再做那個，由上而下。第二是賦值：`x = 7` 表示把值 7 存進名為 x 的盒子裡，而後面的 `x = x + 1` 會讀取舊內容、加一，再把結果寫回同一個盒子。

第三是條件分支：`if 條件 then ... else ...` 根據一個是非判斷選擇一條分支。第四是迴圈：`for` 迴圈重複固定次數，`while` 迴圈則在條件持續為真時不斷重複。第五是呼叫：呼叫另一個具名程序，甚至呼叫自己（遞迴），並使用它回傳的東西。讀懂任何程式都化簡成辨認這五樣，並對每一樣問：它到底對盒子裡的值做了什麼？

LinearSearch(A, n, key):
  for i = 1 to n:
    if A[i] == key:
      return i        // found it at position i
  return NOT_FOUND    // fell off the end

六行裡涵蓋全部五種動作：一個呼叫簽名、一個 for 迴圈、一個 if 判斷、兩個 return，以及它們之間隱含的順序。

用手追蹤它——征服恐懼的唯一習慣

最強大的閱讀技巧只有一個：追蹤——挑一個極小的具體輸入，扮演電腦，把每一行執行後每個變數的值都寫下來。關鍵在於，你是針對成本模型那幾篇講的RAM 模型在模擬——一台機器上，讀寫一個變數、比較兩個數、做一次算術運算，各算一個花常數時間的基本步驟。所以追蹤不是含糊的揮手，而是你一次執行一個定義明確的步驟，把它們寫在紙上。

挑一個小輸入。對上面的 LinearSearch，取 A = [4, 8, 5]、n = 3、key = 5。
以 i = 1 進入迴圈：判斷 A[1] == key，也就是 4 == 5？否。所以不 return，迴圈往前推進。
現在 i = 2：判斷 8 == 5？又是否。再往前推進一次。
現在 i = 3：判斷 5 == 5？是——執行 `return i`，交回 3，演算法停止。
拿輸出對照問題做合理性檢查：位置 3 確實放著 key。追蹤結果與規格相符，這是程式正確的第一個跡象。

注意追蹤還揭露了什麼：在這個輸入上，迴圈本體跑了三次。因此追蹤正是分析的入口——一旦你看出本體跑了幾次，你其實已經在數迴圈迭代次數了，而那是計算執行時間的原料。單一次追蹤本身證明不了一般情況（它只是一個輸入，不是全部），但它讓機制變得鮮明，而鮮明的機制就容易推理。

讀迴圈：不變量的視角

追蹤一個輸入能讓你相信迴圈跑一次是對的。但要理解它為什麼永遠對，就要透過迴圈不變量的視角來看它——一個在迴圈每次即將檢查條件時都成立、與輸入無關的陳述。對 LinearSearch，這個不變量是：「key 不出現在位置 1 到 i-1 的任何地方。」迴圈開始前那個範圍是空的，所以它顯然成立；每一次沒有 return 的迭代，都靠多檢查並排除一個位置來維持它。

這個不變量的想法不是旁門左道，而是讀迴圈、信任迴圈的標準方式，本階梯後面有一整篇專門把它變成滴水不漏的證明。現在你只要練習這個閱讀動作：每遇到一個迴圈，就停下來問：「每一回合的開頭有什麼是成立的？」這一個問題，就能把一團令人生畏的重複，化成一句你腦中拿得住的平靜句子。

信任任何片段之前的誠實提醒

虛擬碼的自由是有代價的：因為它不會被編譯器執行，沒有任何東西逼它完整、甚至正確。一段片段可能悄悄假設陣列非空、索引從 1 開始、`key` 有合理的型別，或某個輔助函式恰好做了它名字暗示的事。好的虛擬碼會把這些假設講明；草率的虛擬碼把它們留成陷阱。無懼地讀，不代表不帶懷疑地讀——而是知道該檢查什麼。

兩個邊界問題能抓出大多數錯誤。第一是邊緣：空輸入會怎樣？n = 0 呢？最前與最後一個索引呢？把這些情況明確追蹤一遍——差一錯誤就藏在那裡。第二是終止：每個迴圈最終都必須停下來。`for i = 1 to n` 是安全的，因為 i 朝 n 前進；但 `while` 迴圈只有在某個量可證明地朝停止點縮小時才會終止。如果你說不出是什麼在縮小，就還不能信任這個迴圈。

最後，記住你正在哪個尺度上閱讀。輸入的大小——輸入規模 n——是後面每個成本主張用來衡量的基準，所以讀的時候要不斷問：「這裡的 n 是什麼，工作量如何隨 n 增長而增長？」這個習慣會悄悄把這項地基層的閱讀技能，接到後面的一切：數步驟的成本模型，以及追問哪些輸入會讓步數變大的最壞／平均／最佳情況視角。虛擬碼只是地圖；追蹤、不變量、邊緣與終止，才是你真正學會在上面行走的方法。