理论与进阶专题
递推关系
递推关系用「解决更小规模的同一个问题需要多少代价」来描述「解决规模为 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 界。
又称
另见