理論與進階主題
遞迴關係
遞迴關係用「解決更小規模的同一個問題需要多少代價」來描述「解決規模為 n 的問題需要多少代價」。它是遞迴的天然語言：如果一個演算法的做法是把輸入拆成幾塊、再對這些塊呼叫自己，那麼它的執行時間就滿足一個引用自身的方程式。我們把總工作量記為 T(n)，其中 T 代表「時間（time）」，n 是輸入規模。
最經典的例子是合併排序。要對 n 個元素排序，它先把它們分成兩半，對每一半排序，再把兩段已排好的合併起來。對每一半排序是規模減半的同一個問題，因此各需 T(n/2)；合併那一步要把全部 n 個元素走一遍，代價為 O(n)。合起來就得到 T(n) = 2T(n/2) + O(n)。這個遞迴式本身還沒告訴你答案——它告訴你工作量的「形狀」，你仍需把它「解」出來，才能得到像 O(n log n) 這樣乾淨的界。
要讓一個遞迴完整，需要兩樣東西。其一是基準情形：小到可以不再遞迴、直接處理的輸入，比如單個元素時 T(1) = O(1)。沒有基準情形，遞迴就會無止境地展開下去。其二是求解的方法——畫出遞迴樹並把每一層的工作量加起來，或先猜一個界再用歸納法證明，又或直接套用現成的公式（如主定理）。遞迴式是問題，閉式的大 O 才是答案。
// merge sort: cost of size n in terms of size n/2
long long T(long long n) {
if (n <= 1) return 1; // base case: T(1) = O(1)
return 2 * T(n / 2) + n; // two halves + an O(n) merge
}
// the equation T(n) = 2T(n/2) + n is the recurrence;
// its closed-form solution is O(n log n).T(n) = 2T(n/2) + O(n)，基準情形 T(1) = O(1)，解得 O(n log n)。
遞迴式描述的是代價；把它解出來（遞迴樹、歸納法或主定理）才能化成一個乾淨的大 O 界。
又稱
另見