大O的和與積規則

一旦你能界住程式的個別片段，就需要規則把這些界黏起來：先做一件事再做另一件（一個和）的成本是多少？把一件事嵌進另一件（一個積）又是多少？兩條簡單規則涵蓋你會做的幾乎所有分析，而它們正是把逐行讀程式碼變成單一大O的方法。

和規則：若你跑一個花 O(f) 的區塊、接著跑一個花 O(g) 的區塊，總和是 O(f + g)，可化簡為 f 與 g 中較大者的 O。這是因為對大的 n，較大的函數主導：O(n) 接 O(n^2) 是 O(n^2)，線性部分被吞掉。這正是我們在 n^2 + n + 1 這種和中只保留主導項的形式理由。積規則：若你對 O(f) 次重複中的每一次，做一件花 O(g) 的事——一個跑 f 次、每趟內部做 g 工作的迴圈——總和是 O(f 乘 g)。一個 n 次迭代、每次做 O(n) 工作的迴圈是 O(n 乘 n) = O(n^2)。這些規則也讓你處理常數乘函數：O(c 乘 f) = O(f)，因為常數倍率消失。

合起來，這些把分析變成記帳。循序的程式碼：把成本相加並保留最大者。巢狀的程式碼：把成本相乘。常數倍縮放：忽略它。一個微妙的誠實提醒：和規則只在被加的區塊「數量為常數」時才保留最大值。若你加的是逐漸增多的項——比如第 i 次迭代花 i，而你對 i 從 1 到 n 求和——你不能只取最大項 n；你必須真的把它們加總，得到 n(n+1)/2 = Theta(n^2)，而非 Theta(n)。仔細計數迴圈迭代正是這個區別所在之處。