时间复杂度的递推公式

时间复杂度的递推公式通常用于分析递归算法的时间复杂度。递归算法的时间复杂度可以通过 递归关系（Recurrence Relation） 来表示，然后通过数学方法（如递归树、主定理、展开法等）来求解。

1. 常见递归关系及求解方法

以下是几种常见的递归关系及其对应的时间复杂度：

(1) 分治算法（Divide and Conquer）

许多分治算法（如归并排序、快速排序、二分查找等）的时间复杂度可以表示为：

$$T(n)=a\cdot T\left(\frac{n}{b}\right)+f(n)$$

其中：

• $a$：子问题的个数

• $\frac{n}{b}$：子问题的规模

• $f(n)$：分解和合并的代价

求解方法：主定理（Master Theorem）

主定理适用于形如 $T(n)=aT(n\mathrm{/}b)+f(n)$ 的递归关系，其解为：

• 如果 $f(n)=O(n^{{\log }_{b}a-ϵ})$，则 $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$

• 如果 $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$，则 $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\log n)$

• 如果 $f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+ϵ})$，且 $af(n\mathrm{/}b)\le cf(n)$，则 $T(n)=\mathrm{\Theta }(f(n))$

例子：

• 归并排序：$T(n)=2T(n\mathrm{/}2)+O(n)$ → $T(n)=O(n\log n)$

• 二分查找：$T(n)=T(n\mathrm{/}2)+O(1)$ → $T(n)=O(\log n)$

• 主定理的直观理解

• 情况	比较 $f(n)$ 和 $n^{{\log }_{b}a}$	结果
  1	$f(n)$ 小得多	$\mathrm{\Theta }(n^{{\log }_{b}a})$
  2	$f(n)$ 相同量级	$\mathrm{\Theta }(n^{{\log }_{b}a}\log n)$
  3	$f(n)$ 大得多	$\mathrm{\Theta }(f(n))$

(2) 线性递归（Linear Recurrence）

某些递归算法每次递归调用只减少一个固定规模（如斐波那契数列）：

$$T(n)=T(n-1)+T(n-2)+O(1)$$

求解方法：特征方程法

• 先写出特征方程，然后求解通解。

• 斐波那契数列：$T(n)=T(n-1)+T(n-2)$ → 时间复杂度 $O(2^n)$

(3) 树形递归（Tree Recursion）

某些递归算法会多次调用自身（如暴力递归）：

$$T(n)=a\cdot T(n-1)+f(n)$$

求解方法：展开法

• 逐层展开递归关系，观察规律。

• 例子：汉诺塔问题 $T(n)=2T(n-1)+1$ → $T(n)=O(2^n)$

2. 常见递归关系的时间复杂度总结

3. 如何求解递归关系？

(1) 递归树法

• 画出递归调用的树结构，计算每层的工作量，然后求和。

• 例子：归并排序 $T(n)=2T(n\mathrm{/}2)+n$ 的递归树：

• 每层的工作量：$n$

• 树高：$\log n$

• 总工作量：$n\log n$

(2) 主定理

适用于分治算法的递归关系，直接套用主定理公式。

(3) 展开法

• 逐层展开递归关系，观察模式。

• 例子：汉诺塔问题：

  $$T(n)=2T(n-1)+1$$

  展开后：

  $$T(n)=2(2T(n-2)+1)+1=4T(n-2)+2+1$$

  最终发现 $T(n)=O(2^n)$。

4. 总结

• 分治算法（如归并排序、快速排序）通常用 主定理 求解。

• 线性递归（如斐波那契数列）可以用 特征方程法 求解。

• 树形递归（如汉诺塔问题）可以用 展开法 或 递归树法 求解。

掌握这些方法后，可以轻松分析大多数递归算法的时间复杂度！