算法基础（十二）——主方法：快速求解常见递归式

1. 定位导航

分治算法经常会产生递归式。

例如：

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

这些递归式看起来相似，但结果可能完全不同：

O(n log n) O(n) O(n²)

主方法就是一种快速判断工具。

它不需要每次完整画递归树，而是通过比较两个关键量来判断结果。

2. 概念术语

关键澄清：

1. 主方法不是所有递归式都能用。
2. 它主要适用于T(n)=aT(n/b)+f(n)这种形式。
3. 判断关键是比较f(n)和n^(log_b a)。
4. 不要只看a和b，f(n)经常决定最终结果。

3. 主方法解决哪类问题

主方法适用于形如：

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

的递归式。

其中：

• a表示子问题个数；
• n/b表示每个子问题的规模；
• f(n)表示除了递归子问题之外，本层额外做的工作。

比如归并排序：

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

对应关系是：

4. 核心比较对象：f(n) 与 n^(log_b a)

主方法最关键的一步是计算：

n log ⁡ b a n^{\log_b a}nlogb​a

这个量可以理解为递归树中“子问题扩张出来的基准增长”。

然后比较：

f(n) 和 n^(log_b a)

谁更强。

以归并排序为例：

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

这里：

a = 2 , b = 2 a = 2,\quad b = 2a=2,b=2

所以：

n log ⁡ b a = n log ⁡ 2 2 = n n^{\log_b a} = n^{\log_2 2} = nnlogb​a=nlog2​2=n

而：

f ( n ) = n f(n) = nf(n)=n

两者同级，所以属于情况 2。

结果是：

T ( n ) = Θ ( n log ⁡ n ) T(n) = \Theta(n \log n)T(n)=Θ(nlogn)

5. 主方法的三种情况

主方法可以分成三种情况。

5.1 情况 1：f(n) 更小

如果：

f ( n ) f(n)f(n)

比：

n log ⁡ b a n^{\log_b a}nlogb​a

小一个多项式级别，那么递归成本主导。

结果是：

T ( n ) = Θ ( n log ⁡ b a ) T(n) = \Theta(n^{\log_b a})T(n)=Θ(nlogb​a)

直觉：

越往下递归，子问题数量增长带来的成本更重要。

5.2 情况 2：f(n) 与基准项同级

如果：

f ( n ) = Θ ( n log ⁡ b a ) f(n) = \Theta(n^{\log_b a})f(n)=Θ(nlogb​a)

那么每一层贡献差不多。

结果是：

T ( n ) = Θ ( n log ⁡ b a log ⁡ n ) T(n) = \Theta(n^{\log_b a} \log n)T(n)=Θ(nlogb​alogn)

直觉：

每一层都差不多，总共约 log n 层，所以多乘一个 log n。

5.3 情况 3：f(n) 更大

如果：

f ( n ) f(n)f(n)

比：

n log ⁡ b a n^{\log_b a}nlogb​a

大一个多项式级别，并且满足一定的正则条件，那么本层额外工作主导。

结果是：

T ( n ) = Θ ( f ( n ) ) T(n) = \Theta(f(n))T(n)=Θ(f(n))

直觉：

上层合并成本已经足够大，递归子问题反而不是主导。

6. 动态推演：三种情况如何判断

下面用动态图观察三种关系。

可以这样理解：

• 情况 1：f(n)比基准项更小，递归展开更重要；
• 情况 2：f(n)和基准项同级，每层成本接近；
• 情况 3：f(n)比基准项更大，当前层工作更重要。

7. 典型例子

7.1 例子一：T(n)=2T(n/2)+n

这里：

a = 2 , b = 2 , f ( n ) = n a=2,\quad b=2,\quad f(n)=na=2,b=2,f(n)=n

基准项：

n log ⁡ 2 2 = n n^{\log_2 2}=nnlog2​2=n

f(n)和基准项同级，属于情况 2。

所以：

T ( n ) = Θ ( n log ⁡ n ) T(n)=\Theta(n\log n)T(n)=Θ(nlogn)

7.2 例子二：T(n)=2T(n/2)+1

这里：

a = 2 , b = 2 , f ( n ) = 1 a=2,\quad b=2,\quad f(n)=1a=2,b=2,f(n)=1

基准项：

n log ⁡ 2 2 = n n^{\log_2 2}=nnlog2​2=n

f(n)比基准项小，属于情况 1。

所以：

T ( n ) = Θ ( n ) T(n)=\Theta(n)T(n)=Θ(n)

7.3 例子三：T(n)=2T(n/2)+n²

这里：

a = 2 , b = 2 , f ( n ) = n 2 a=2,\quad b=2,\quad f(n)=n^2a=2,b=2,f(n)=n2

基准项：

n log ⁡ 2 2 = n n^{\log_2 2}=nnlog2​2=n

f(n)比基准项大，属于情况 3。

所以：

T ( n ) = Θ ( n 2 ) T(n)=\Theta(n^2)T(n)=Θ(n2)

8. 判断流程

使用主方法时，可以按照下面流程来。

第一步：确认递归式形式

先确认是否形如：

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

如果形式不匹配，不要硬套。

第二步：计算基准项

计算：

n log ⁡ b a n^{\log_b a}nlogb​a

第三步：比较强弱

比较：

f(n) 与 n^(log_b a)

谁更大、谁更小，或者是否同级。

第四步：套用三种情况

根据比较结果，选择情况 1、情况 2 或情况 3。

9. 代码实践：自动套用简单主方法

下面写一个简单的 Python 小工具，只处理f(n)=n^k这种常见形式。

importmathdefmaster_method(a,b,k):""" 处理递归式： T(n) = aT(n/b) + n^k 参数： a: 子问题个数 b: 子问题缩小倍数 k: f(n)=n^k 中的 k """critical=math.log(a,b)print(f"a ={a}, b ={b}, f(n) = n^{k}")print(f"基准指数 log_b(a) ={critical:.4f}")ifk<critical:print("情况 1：f(n) 更小")print(f"T(n) = Θ(n^{critical:.4f})")elifabs(k-critical)<1e-9:print("情况 2：f(n) 与基准项同级")print(f"T(n) = Θ(n^{critical:.4f}log n)")else:print("情况 3：f(n) 更大")print(f"T(n) = Θ(n^{k})")master_method(2,2,1)print()master_method(2,2,0)print()master_method(2,2,2)

输出示例：

a = 2, b = 2, f(n) = n^1 基准指数 log_b(a) = 1.0000 情况 2：f(n) 与基准项同级 T(n) = Θ(n^1.0000 log n) a = 2, b = 2, f(n) = n^0 基准指数 log_b(a) = 1.0000 情况 1：f(n) 更小 T(n) = Θ(n^1.0000) a = 2, b = 2, f(n) = n^2 基准指数 log_b(a) = 1.0000 情况 3：f(n) 更大 T(n) = Θ(n^2)

这个工具不是完整的数学证明器，但可以帮助快速建立判断直觉。

10. 常见误区

误区一：看到递归式就硬套主方法

不是所有递归式都能直接套。

例如：

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

它不是aT(n/b)+f(n)形式，就不适合直接用这个版本的主方法。

误区二：算错 log_b a

主方法的核心基准项是：

n log ⁡ b a n^{\log_b a}nlogb​a

如果这里算错，后面判断都会错。

误区三：忘记情况 2 里的 log n

当：

f ( n ) = Θ ( n log ⁡ b a ) f(n)=\Theta(n^{\log_b a})f(n)=Θ(nlogb​a)

结果不是简单的：

Θ ( n log ⁡ b a ) \Theta(n^{\log_b a})Θ(nlogb​a)

而是：

Θ ( n log ⁡ b a log ⁡ n ) \Theta(n^{\log_b a}\log n)Θ(nlogb​alogn)

误区四：只凭直觉比较大小

比较f(n)和基准项时，要看增长量级，不是看某个小规模下的数值。

11. 现代延伸

主方法不仅用于排序，也常用于分析很多分治或递归系统。

工程里很多“拆分—递归处理—合并”的流程，都可以先写出递归式，再用类似方法估算增长趋势。

比如大文件分块处理、分布式聚合、多级归并、并行任务树，都可以借助这种思路快速判断瓶颈来自哪里。

12. 思考题

1. 主方法适用于哪类递归式？
2. T(n)=2T(n/2)+n为什么是情况 2？
3. T(n)=2T(n/2)+1为什么是情况 1？
4. T(n)=2T(n/2)+n²为什么是情况 3？
5. 为什么情况 2 的结果要多乘一个log n？
6. T(n)=3T(n/3)+n的复杂度是多少？

13. 本篇小结

本篇讲清楚了主方法。

核心结论是：

• 主方法用于快速求解T(n)=aT(n/b)+f(n)类型的递归式；
• a表示子问题个数；
• b表示子问题规模缩小倍数；
• f(n)表示本层额外工作；
• 核心比较对象是f(n)和n^(log_b a)；
• 情况 1：f(n)更小，结果看基准项；
• 情况 2：两者同级，结果多乘一个log n；
• 情况 3：f(n)更大，结果看f(n)；
• 使用前要先确认递归式形式是否匹配。

主方法可以理解成递归树分析的快捷版。

递归树帮你看懂原因，主方法帮你快速得到结果。