目錄
這是 Stanford CS161 導讀的第 2 篇，對應 Stanford CS161, Winter 2026, Lecture 1。這堂課在 2026 年 1 月 5 日由 Ellen Vitercik 主講，官方題目是 Why are you here?。公開材料有講義、70 頁投影片，以及課程頁連出去的 notebook 與概念檢核；本文實際使用講義與投影片。錄影只能從 Canvas 進入，我沒有把它當成已讀來源。
第一講不是把演算法定義背一遍。它選了一個每個人都會做的工作：整數乘法。你小學就知道直式乘法，但「會算」和「知道這個算法在輸入變大時要付出多少」是兩件事。這堂課用同一個例子串起三個課程目標：設計一個不同的算法、分析它的成長率、把理由寫到別人可以檢查。
三個目標不是三份清單
投影片把 CS161 的目標寫成 Design、Analysis、Communication。它們在 Karatsuba 例子裡同時出現：
- 設計：把大乘法拆成較小乘法，找出能少做一次遞迴的方法。
- 分析：不能只跑幾筆測試，要寫出輸入大小與工作量的關係。
- 溝通：每個符號代表什麼、哪一步用到什麼恆等式、忽略了哪些成本，都要說得清楚。
這也是「Why are you here?」的真正答案。演算法不只是一袋程式技巧。作業系統的排程、網路的最短路徑、機器學習的幾何搜尋、密碼學的數論運算，都會回到同一種提問：問題能不能拆？資訊最少要看多少？一個看似自然的做法，是否其實重複了不必要的工作？
Slides 也從 al-Khwarizmi 講到 algorithm 的詞源。這段不是裝飾：數字表示法本身就是資料結構。羅馬數字讓乘法彆扭，十進位位值制讓「拆高位與低位」成為可操作的代數。演算法從來不只依賴步驟，也依賴輸入如何表示。
為什麼不用毫秒判斷快慢
假設要比較兩個乘法程式。第一個在某台筆電跑 6 毫秒，第二個跑 10 毫秒，能不能宣布第一個演算法比較快？不能。這個數字同時混進程式語言、實作品質、處理器、快取與測試資料；換一台機器，排名可能就變。
CS161 改問另一件事：當輸入從 n 位變成 2n 位，工作量如何成長？直式乘法會讓第一個數的每一位，分別乘上第二個數的每一位。兩邊各有 n 位，位數配對共有約 n² 個。還要處理進位與相加，但整體仍隨平方成長。
第一講只先給直覺版的 big-O：它描述輸入夠大時，執行時間如何隨輸入規模伸展。正式定義留到第二講。眼前只需要抓住一件事：常數差異不會抵銷不同的成長率。即使一個 n^1.6 程式起步較慢，n 夠大後仍會超過 n² 程式。
這不表示常數永遠不重要。使用者當然會在意瀏覽器慢七倍；只是演算法課此刻要隔離的是「策略本身」的規模效應。實測回答這份實作今天跑多快，漸近分析回答問題放大後哪種策略會先崩掉。
第一次分治：拆了，卻沒有省
分治法的基本節奏是：拆成較小的同型子問題、遞迴解掉、再組合答案。令 x、y 都是 n 位數，暫時假設 n 是偶數。把兩個數各切成高、低兩半：
x = 10^(n/2) a + b
y = 10^(n/2) c + d展開乘積：
xy = 10^n ac + 10^(n/2)(ad + bc) + bd以 1234 × 5678 為例，a=12、b=34、c=56、d=78。一個 4 位數乘法變成 12×56、12×78、34×56、34×78 四個 2 位數乘法，再把結果移位相加。
這確實是分治，卻沒有更快。若一路遞迴到一位數，4 位數輸入產生 16 個一位數乘法；8 位數產生 64 個。一般來說，切半 log₂n 次後，葉節點數是：
4^(log₂ n) = n^(log₂ 4) = n²把執行時間寫成遞迴式，就是：
T(n) = 4T(n/2) + O(n)4T(n/2) 是四個半尺寸乘法，O(n) 是切割、加法與組合。第一講先用葉節點數量抓主導項；第三講才會把這類遞迴式正式解完。重要的不是「分治一定快」，而是分治後有幾個子問題。如果只是把直式乘法的每一對位數重新排成樹，工作一件也沒少。
Karatsuba 真正省掉的是哪一次乘法
展開式需要 ac、bd 與 ad+bc。直覺做法分別計算 ad、bc，所以總共四次遞迴乘法。Karatsuba 的關鍵觀察是：組合答案只需要交叉項的和，不需要單獨知道兩項。
先算三個乘積：
z1 = ac
z2 = bd
z3 = (a+b)(c+d)因為：
z3 = ac + ad + bc + bd所以：
ad + bc = z3 - z1 - z2完整組合式變成：
xy = 10^n z1 + 10^(n/2)(z3-z1-z2) + z2拿 1234 × 5678 手算一次：
z1 = 12×56 = 672
z2 = 34×78 = 2652
z3 = 46×134 = 6164
cross = 6164-672-2652 = 2840
xy = 672×10000 + 2840×100 + 2652
= 7,006,652這個例子也直接說明正確性。Karatsuba 沒有猜答案；它只用代數恆等式重建原本的四項展開。若遞迴呼叫能正確算出三個較小乘積，組合式就必然回到 xy。官方材料沒有把這段寫成正式的遞迴歸納證明，所以本文也只把證明範圍說到代數與遞迴假設，不冒充課堂給了完整形式化證明。
從四個分支降到三個，差多少
Karatsuba 的遞迴式是：
T(n) = 3T(n/2) + O(n)先忽略每層線性工作，切半 log₂n 次後，底層一位數乘法共有：
3^(log₂ n)
= n^(log₂ 3)
≈ n^1.585這就是第一講投影片常寫成 n^1.6 的原因：它是便於閱讀的近似上界，不是精確指數。和 n² 相比，少掉的不是一個固定數量，而是遞迴樹每個內部節點都少長一個孩子。差距會一層一層累積。
空間方面，公開講義沒有建立正式模型。若直接建立切片與中間大整數，會有遞迴堆疊與暫存空間；若用索引、重用緩衝區，常數會不同。因此這堂課能支持的是時間成長率的主結論，不支持一個未指定實作的精確空間界。
Notebook 實驗為何不能取代理論
官方課程頁連到一份 Karatsuba notebook；目前連結實際指向 Winter 2025 的課程輔助 repository，而不是 Winter 2026 notes 本身。Notebook 完整實作三個版本：逐位數的 grade-school multiplication、分成四個半尺寸乘法的第一版 divide-and-conquer，以及只做三個半尺寸乘法的 Karatsuba。它先以 1234567×654321 對照 Python 內建乘法做基本檢查，再對不同位數重複計時並畫圖。
這份實驗很適合把抽象 recurrence 接回程式，但也刻意暴露量測邊界。四分支版本的圖在二的冪附近出現奇怪行為，grade-school 與 recursive 版本在有限範圍內也未必容易看出漸近勝負；notebook 因此直接說，需要數學分析才能理解 n 很大時的行為。量測會混入 Python list 操作、整數轉 digits、padding、遞迴函式成本與硬體噪音，這些都不是「遞迴乘法次數」本身。
Notebook 的規則也比一般 Python 算術更窄：只允許內建的一位數乘法，但允許大型加法。這正好說明成本模型不能省略。課堂的 O(n²) 與 O(n^{log₂3}) 比較，是在位數操作模型下追蹤主要工作；它不是聲稱 notebook 每一行都有常數成本，也不是說 Karatsuba 對所有小輸入都一定量到較快。
三個版本還提供一個很乾淨的控制實驗。第一版分治與 Karatsuba 都要切割、補零、遞迴及重組，主要結構相近；關鍵差異是每個節點做四次或三次子乘法。若只拿 Karatsuba 和完全不同語言、不同資料表示的系統乘法比較，很難知道差距來自算法還是工程。並排閱讀這兩個 recursive functions，則能把因果問題縮小到「以額外加減換掉一個遞迴乘法」。
不過 notebook 的測試只示範單一正確性案例，程式註解也提醒真實測試應更完整。負數、前導零、奇數位切割、大量隨機案例與跨過 cutoff 的邊界，都需要另外測。一次輸出與 Python 相同只能增加信心，不能取代對所有輸入的歸納證明。反過來，代數證明也不能告訴我們 Python 實作是否有 indexing bug。實驗檢查 implementation，證明檢查 algorithm；兩者的失敗模式不同。
因此合理的閱讀順序是：先用三個實作看見工作如何被重排，再用 recurrence 解釋曲線長期形狀，最後用 benchmark 找特定環境的 crossover。量測能檢查實作是否像推導所預期地成長，理論則解釋為何三個遞迴分支最終會勝過四個；它們互補，不能互相冒充。
這份分析刻意略過什麼
第一講自己多次提醒它「算得很鬆」。這些提醒不是瑕疵，而是下一講的入口：
a+b可能比a多一位，所以子問題不一定恰好是n/2位。- 暫時假設
n是 2 的冪；其他長度可補前導零，但程式仍要處理奇數切割。 - 把十進位移位、切割、加減視為線性工作，沒有逐一固定基本操作。
- 葉節點分析先忽略較高層工作；要證明它不改變主導階，需要後續的遞迴式工具。
- 投影片的偽程式是設計圖，不是可直接執行的完整實作。
因此最常見的誤用，是看到 3T(n/2) 就直接宣布所有成本都是 n^1.585。正確說法是：在大整數以位數 n 表示、加減與切割成本受線性界控制的模型下，正式解 3T(n/2)+O(n) 才得到這個上界。
另一個誤用是把 Karatsuba 寫成「任何大小都比直式乘法快」。漸近較快不代表小輸入的實測一定較快；多次加減、配置與遞迴呼叫都有常數成本。這堂課的判決是大規模成長率較好，不是替所有實作指定切換門檻。
乘法史在這堂課扮演的角色
講義最後提到 Toom–Cook、Schönhage–Strassen、Fürer，以及 Harvey–van der Hoeven 的 O(n log n) 結果。這一串名稱不是考試清單，而是用來推翻「小學問題早就結束了」的直覺。改善演算法的方式也不只換快一點的硬體；重新安排資訊，可能直接改變成長率。
課程把 O(n log n) 稱為被猜測的最佳量級，但沒有在第一講證明，也沒有要求學生掌握後續乘法演算法。本文因此只保留它作為課堂收尾，不延伸評論研究現況。若要追最新下界或實作，應另讀原始論文，不能拿這堂導論的歷史頁當完整研究綜述。
這一講在十八講裡的位置
Lecture 1 建立的是一種不信直覺的習慣。你可以正確算出答案，算法仍可能浪費工作；你可以把問題拆開，分治仍可能沒有改善；你可以畫出實測曲線，仍未必知道換硬體後是否成立。
下一講會把今天刻意模糊的詞正式化：Big-O、Big-Omega、Big-Theta、最壞情況分析，以及如何證明 InsertionSort、MergeSort 正確。第三講再處理今天留下的遞迴式。換句話說，Karatsuba 不是孤立技巧，而是後面兩講的共同測試案例。
如果要檢查自己是否真的讀懂，不必先寫程式。拿紙把 1234×5678 的三個子乘積算完，然後回答兩題：為什麼交叉項能被重建？為什麼四分支樹的葉數是 n²、三分支樹卻是 n^{log₂3}？能把這兩句寫給沒看過投影片的人讀懂，才同時碰到了設計、分析與溝通。
延伸
實作 Karatsuba 時，常見做法不是一路遞迴到一位數，而是在輸入夠小時切回直式乘法。這是工程上的混合策略：大輸入利用較好的漸近階，小輸入避開遞迴與暫存成本。Winter 2026 的公開講義沒有指定門檻，本文也不給一個假裝通用的數字；門檻應由數字表示、語言與硬體上的基準測試決定。
另一個值得自己動手的延伸，是分別記錄「一位數乘法次數」與「總牆鐘時間」。前者會貼近遞迴樹預測，後者會混入直譯器、配置與快取。把兩張圖放在一起，正好能看見分析模型解釋了什麼，又沒有解釋什麼。
參考資料
Loading...