时间复杂度分析

1. 引言

递归算法的时间复杂度通常用递归式表示。本文介绍三种分析递归式的工具：递归树法、主定理与 Akra-Bazzi 定理，并通过实例帮助读者掌握递归复杂度的分析方法。

2. 时间复杂度基础

2.1 什么是时间复杂度

时间复杂度描述算法执行时间随输入规模增长的变化趋势，常用大 O 记号表示上界。常见复杂度从低到高：O(1)O(1)O(1)、O(log⁡n)O(\log n)O(logn)、O(n)O(n)O(n)、O(nlog⁡n)O(n \log n)O(nlogn)、O(n2)O(n^2)O(n2)、O(2n)O(2^n)O(2n)。

下面列出常见算法的时间复杂度，便于对照记忆：

递归算法的时间复杂度用递归式表示，如归并排序：

T(n)=2T(n/2)+O(n) T(n) = 2T(n/2) + O(n)T(n)=2T(n/2)+O(n)

含义：解决规模为nnn的问题，需解决 2 个规模为n/2n/2n/2的子问题，再加上合并所需的O(n)O(n)O(n)时间。

3. 递归树法

3.1 基本思想

递归树法把递归式的展开过程画成一棵树，每个节点代表一个子问题的开销，把所有层开销累加即得总复杂度。以归并排序为例：

T(n)=2T(n/2)+O(n) T(n) = 2T(n/2) + O(n)T(n)=2T(n/2)+O(n)

递归树如下：

n / \ n/2 n/2 / \ / \ n/4 n/4 n/4 n/4

每层开销都是nnn，树高为log⁡2n\log_2 nlog2​n，因此总复杂度为Θ(nlog⁡n)\Theta(n \log n)Θ(nlogn)。

3.2 递归树法的步骤

1. 展开递归式：把每层的分解与合并开销写在节点上。
2. 计算每层总开销：将同一层所有节点开销相加。
3. 确定树高：子问题规模从 n 缩小到常数所需的层数。
4. 累加所有层：将各层开销求和。

3.3 递归树法示例

示例一：二分查找

T(n)=T(n/2)+O(1) T(n) = T(n/2) + O(1)T(n)=T(n/2)+O(1)

每层只有一个节点，开销为O(1)O(1)O(1)，树高为log⁡2n\log_2 nlog2​n，因此T(n)=Θ(log⁡n)T(n) = \Theta(\log n)T(n)=Θ(logn)。

示例二：子问题规模不等

T(n)=T(n/3)+T(2n/3)+O(n) T(n) = T(n/3) + T(2n/3) + O(n)T(n)=T(n/3)+T(2n/3)+O(n)

每层总开销为nnn，树高由最长路径决定，为log⁡3/2(n)\log_{3/2}(n)log3/2​(n)，因此T(n)=Θ(nlog⁡n)T(n) = \Theta(n \log n)T(n)=Θ(nlogn)。

递归树法直观但不够严谨，更严格的证明通常借助主定理或 Akra-Bazzi 定理。

4. 主定理（Master Theorem）

4.1 主定理的适用条件

主定理适用于形如下式的递归式：

T(n)=aT(n/b)+f(n) T(n) = aT(n/b) + f(n)T(n)=aT(n/b)+f(n)

其中 a ≥ 1 为子问题个数，b > 1 为规模缩减比例，f(n) 为分解与合并的开销。

4.2 主定理的三种情况

主定理通过比较f(n)f(n)f(n)与nlog⁡ban^{\log_b a}nlogb​a的渐近大小关系划分三种情况。
情况一：递归主导

当f(n)=O(nlog⁡ba−ε)f(n) = O(n^{\log_b a - \varepsilon})f(n)=O(nlogb​a−ε)（ε>0\varepsilon > 0ε>0）时：

T(n)=Θ(nlog⁡ba) T(n) = \Theta(n^{\log_b a})T(n)