时间复杂度

情况1，使用累加法求解

递推形式	典型场景	复杂度
$T(n)=T(n-1)+O(1)$	每次规模减 1	$O(n)$
$T(n)=T(n-1)+O(n)$	每层再做一次线性操作	$O(n^2)$
$T(n)=T(n-1)+O(n^k)$	逐层递减	$O(n^{k+1})$

第二类

递推形式	典型场景	复杂度
$T(n)=T(n/2)+O(1)$	二分、倍增	$O(\log n)$
$T(n)=T(n/2)+O(n)$	每层扫描整个当前区间	$O(n)$

第三类

递推形式	典型场景	复杂度
$T(n)=2T(n-1)+O(1)$	每层产生两个规模 $n-1$ 的问题	$O(2^n)$
$T(n)=2T(n/2)+O(1)$	二叉递归	$O(n)$
$T(n)=2T(n/2)+O(n)$	归并排序	$O(n\log n)$
$T(n)=2T(n/2)+O(n^2)$	分成两半但合并很重	$O(n^2)$

第四类，使用主定理求解。

递推形式	典型场景	复杂度
$T(n)=aT(n/b)+f(n)$	标准分治	用 Master 定理

例子

递推式	$n^{\log_b^a}$	比较	复杂度
$T(n)=2T(n/2)+1$	$n$	$1\ll n$	$\Theta(n)$
$T(n)=4T(n/2)+n$	$n^2$	$n\ll n^2$	$\Theta(n^2)$
$T(n)=2T(n/2)+n$	$n$	相同	$\Theta(n\log n)$
$T(n)=4T(n/2)+n^2$	$n^2$	相同	$\Theta(n^2\log n)$
$T(n)=2T(n/2)+n^2$	$n$	$n^2\gg n$	$\Theta(n^2)$

注意是具有 $n^\varepsilon$ 这样的多项式级差距。$T(n)=3T(n/4)+n\lg n$ 可以使用主定理求解，而 $T(n) = 2T(n/2) + n\lg n$ 将不能使用一般的主定理求解。