写出递推式 T(n)
你已经会数一个循环的代价了。可一个调用*自身*的函数，代价又是多少？你没法只盯着它看，因为它的工作量取决于同一个问题的更小副本的工作量。诀窍是给这个代价起个名字——叫它 T(n)，即求解规模为 n 的问题所需的时间——然后写一个等式来说：“规模 n 的时间，等于更小那些部分的时间，加上我拆分与合并它们所做的一切。”这个引用自身的等式，就是[[recurrence-relation|递推关系（递推式）]]。
一旦看出规律，把代码读成递推式就是机械活了。每出现一次递归调用，就加一个 T(更小的规模)。然后为该次调用中的非递归工作单独加一项——也就是递归之前或之后发生的循环、比较和合并。最后写一个基准情形（base case）：函数停止递归时的规模，它只花常数时间，T(1) = O(1)。下面是[[merge-sort|归并排序]]，逐行读成它的递推式。
void mergeSort(vector<int>& a, int lo, int hi) {
if (hi - lo <= 1) return; // base case: T(1) = O(1)
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid); // one call on n/2 -> T(n/2)
mergeSort(a, mid, hi); // one call on n/2 -> T(n/2)
merge(a, lo, mid, hi); // scan and merge -> O(n)
}
// Reading the lines: T(n) = 2*T(n/2) + O(n), T(1) = O(1)用展开法求解
在动用定理之前，用老实的办法解一个递推式很有帮助：展开（unrolling）。你把递推式一层层代入自身，直到看出规律，再把各层的工作量加起来。取最简单的递归代价：T(n) = T(n/2) + O(1)——对一半做一次调用，加上常数工作。这正是[[binary-search|二分查找]]：丢掉一半，做一次比较。
T(n) = T(n/2) + 1
= T(n/4) + 1 + 1
= T(n/8) + 1 + 1 + 1
...
= T(n/2^k) + k // after k steps
Stop when n/2^k = 1 => 2^k = n => k = log2(n)
So T(n) = T(1) + log2(n) = O(log n).同一幅图也能解释归并排序，只是账算法变了。画出递归树（recursion tree）：树根是规模为 n 的问题，它的两个孩子是 n/2，孩子的孩子是 n/4，依此类推。这棵树深 log n 层——但在*每一*层上，跨越所有节点的合并加起来都是 O(n)。于是你有 log n 层，每层花 O(n)，总和就是它们的乘积：O(n log n)。
level 0: [ n ] work this level: n
level 1: [n/2] [n/2] work this level: n/2 + n/2 = n
level 2: [n/4][n/4][n/4][n/4] work this level: 4*(n/4) = n
... ... ... ... ... ...
level log n: [1][1][1] ... [1] work this level: n*(1) = n
----------------------------------------------------
log n levels x n per level = O(n log n)把主定理当作菜谱
展开法管用，但很繁琐。[[master-theorem|主定理]]是针对一种特定形式的[[divide-and-conquer|分治]]递推式的捷径：T(n) = a·T(n/b) + f(n)，其中你做 a 次递归调用，每次面对一个小 b 倍的问题，并在递归之外花 f(n) 做拆分与合并的工作。对归并排序，a = 2、b = 2、f(n) = n。该定理把递归本身的增长（由 n 的「以 b 为底 a 的对数」次幂刻画）与 f(n) 的增长相比较，挑出胜者。
Master Theorem (for T(n) = a*T(n/b) + f(n), a >= 1, b > 1)
Let c = log_b(a). Compare f(n) against n^c:
Case 1 f(n) grows slower than n^c -> T(n) = O(n^c)
(the leaves dominate)
Case 2 f(n) grows like n^c -> T(n) = O(n^c * log n)
(every level costs about the same)
Case 3 f(n) grows faster than n^c -> T(n) = O(f(n))
(the root's own work dominates)- 归并排序：T(n) = 2·T(n/2) + n。此处 a = 2、b = 2，故 c = log_2(2) = 1，n^c = n。额外工作 f(n) = n 与 n^c = n 同阶——打平。这是情形 2，得 T(n) = O(n^1 · log n) = O(n log n)。与递归树完全吻合。
- 二分查找：T(n) = 1·T(n/2) + O(1)。此处 a = 1、b = 2，故 c = log_2(1) = 0，n^c = n^0 = 1。额外工作 f(n) = O(1) 与 n^c = 1 同阶——又是打平。仍是情形 2，得 T(n) = O(1 · log n) = O(log n)。和展开法给出的答案一致。
- 尝一口情形 1：T(n) = 8·T(n/2) + n。此时 c = log_2(8) = 3，故 n^c = n^3，远快于 f(n) = n。叶子主导：T(n) = O(n^3)。是递归的分支数、而非每次调用的工作量，决定了代价。