一、搞懂递归算法的核心：先拆“递推关系式”这个坎
很多人学递归算法时，总觉得“时间复杂度”是个摸不着头脑的玄学概念，要么只会套公式，要么套完也不知道为啥对，甚至经常用错。其实要搞懂递归的时间复杂度，第一步不是背主定理，而是先搞明白什么是“递推关系式”——说白了，就是用数学式子把递归算法的工作量拆解清楚。
先给大家举个最常见的递归例子：二分查找。假设我们要在一个长度为n的有序数组里找某个数，二分查找的逻辑是：每次把数组砍成两半，只留可能有目标数的那一半继续找，直到找到或者数组空了。那它的工作量怎么算？我们把“长度为n的数组找目标数的工作量”记成T(n)，那：
- 每次砍数组需要花1步（就是判断中间数和目标数的大小），所以有个1的基础工作量；
- 砍完之后，只需要处理长度为n/2的数组，这部分的工作量就是T(n/2)。
所以二分查找的递推关系式就是：T(n) = T(n/2) + 1，同时有个边界条件：当n=1的时候（数组只剩一个数，要么找到要么没找到，不需要再递归），T(1) = 1。
1.1 怎么从递推关系式推时间复杂度？
刚说的二分查找的递推式，我们可以用“展开法”手动算一遍，这样能直观看到规律。展开法的核心就是把递推式一层一层拆，直到拆到边界条件，然后把所有工作量加起来。
还是拿二分查找举例，我们一步步展开：
- 第一层：T(n) = T(n/2) + 1
- 第二层：把T(n/2)代入，变成T(n) = [T(n/4) + 1] + 1 = T(n/4) + 2
- 第三层：再把T(n/4)代入，变成T(n) = [T(n/8) + 1] + 2 = T(n/8) + 3 ... 每展开一次，n除以2的次数加1，后面的常数项也加1。那什么时候会拆到边界条件？当n除以2的k次后等于1的时候，也就是n/(2^k) = 1，解这个式子的话，k = log2(n)（因为2^k = n，所以k是n的以2为底的对数）。
这时候把k代入，T(n) = T(1) + k = 1 + log2(n)。时间复杂度看的是增长趋势，当n很大的时候，常数1可以忽略，所以二分查找的时间复杂度就是O(logn)，和我们平时背的结论一致。
为了让大家更直观，我们用代码来模拟这个展开过程，这里统一用Python作为技术栈，所有代码都用Python写：
# 技术栈：Python 3.9+
# 模拟二分查找的工作量计算（手动展开递推式）
def calculate_T(n):
# 边界条件：n=1时工作量为1
if n == 1:
return 1
# 递推式：T(n) = T(n/2) + 1
return calculate_T(n // 2) + 1
# 测试n=8（log2(8)=3，所以结果应该是1+3=4）
print(calculate_T(8)) # 输出4，符合我们的推导
# 测试n=16（log2(16)=4，结果应该是1+4=5）
print(calculate_T(16)) # 输出5，验证正确
二、主定理：把递推式的计算标准化，不用每次手动展开
手动展开递推式虽然直观，但如果遇到复杂的递归，比如分治算法（像归并排序、快速排序），展开起来会特别麻烦。这时候就需要主定理——它相当于一个“递推式时间复杂度的速查公式”，只要你的递推式符合主定理的标准形式，就能直接套出时间复杂度，不用再手动拆。
2.1 主定理的标准形式和三个情况
主定理适用于这种标准的递推式：T(n) = a*T(n/b) + f(n)，其中a、b都是大于1的常数，f(n)是一个非负的函数（代表非递归部分的工作量）。
这里先解释一下每个参数的意思，怕大家看不懂：
- a：递归调用的次数。比如二分查找每次只调用1次，所以a=1；归并排序每次把数组拆成两半，左右各调用一次，所以a=2。
- b：每次递归把问题规模缩小的倍数。比如二分查找每次把n砍成一半，所以b=2；如果每次把n砍成三分之一，b就是3。
- f(n)：非递归部分的工作量。比如二分查找每次砍数组花1步，f(n)=1；归并排序最后合并两个有序数组的工作量是O(n)，所以f(n)=n。
主定理根据f(n)和a*T(n/b)的“增长速度”关系，分成三个情况，只要符合其中一种，就能直接得出时间复杂度：
情况1：f(n)的增长比a*T(n/b)慢很多
如果存在一个大于0的常数ε，使得f(n) = O(n^(log_b(a) - ε))，那时间复杂度就是O(n^(log_b(a)))。 举个例子：归并排序的递推式是T(n)=2*T(n/2)+n，这里a=2，b=2，所以log_b(a)=log2(2)=1，n^(log_b(a))=n^1=n。f(n)=n，那f(n)和n的关系是什么？其实情况1的特殊情况是当f(n)是多项式，且次数比log_b(a)小，比如如果f(n)=n^0.5（也就是√n），那√n的增长比n慢，所以时间复杂度就是O(n)。
情况2：f(n)的增长和a*T(n/b)差不多
如果f(n) = Θ(n^(log_b(a)))（Θ是紧确界，意思是增长速度完全一样），那时间复杂度就是O(n^(log_b(a)) * logn)。 最典型的例子就是归并排序：a=2，b=2，log_b(a)=1，n^(log_b(a))=n，f(n)=n，正好符合f(n)=Θ(n)，所以时间复杂度是O(n*logn)，和我们背的结论一致。
情况3：f(n)的增长比a*T(n/b)快很多
如果存在一个大于0的常数ε，使得f(n) = Ω(n^(log_b(a) + ε))，并且满足“正则条件”（就是af(n/b) ≤ cf(n)，c是小于1的常数），那时间复杂度就是O(f(n))。 举个例子：假设递推式是T(n)=2T(n/2)+n^2，这里a=2，b=2，log_b(a)=1，n^(log_b(a))=n，f(n)=n²，n²的增长比n快很多，而且af(n/b)=2*(n/2)²=2*(n²/4)=n²/2 ≤ 0.5*n²（c=0.5<1），满足正则条件，所以时间复杂度是O(n²)。
2.2 主定理的实战应用：归并排序的时间复杂度推导
我们用归并排序来完整走一遍主定理的流程，先给大家看归并排序的Python代码，方便理解：
# 技术栈：Python 3.9+
# 归并排序代码
def merge_sort(arr):
# 边界条件：数组长度<=1时，已经有序，工作量为1
if len(arr) <= 1:
return arr
# 拆分数组为左右两半
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
# 递归排序左右两半：a=2，因为调用了2次
left_sorted = merge_sort(left)
right_sorted = merge_sort(right)
# 合并两个有序数组：非递归部分的工作量f(n)=O(n)
return merge(left_sorted, right_sorted)
def merge(left, right):
# 合并两个有序数组的逻辑，工作量和数组总长度成正比（O(n)）
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 把剩下的元素加进去
result.extend(left[i:])
result.extend(right[j:])
return result
现在推导归并排序的时间复杂度：
- 先写出递推式：T(n) = 2*T(n/2) + n（a=2，b=2，f(n)=n）
- 计算log_b(a)：log2(2)=1，所以n^(log_b(a))=n^1=n
- 对比f(n)和n的关系：f(n)=n，正好等于n，符合情况2的条件
- 所以时间复杂度是O(n^(log_b(a)) * logn) = O(n*logn)
我们也可以用代码来验证这个结论，比如计算不同n下的merge_sort的工作量（这里把merge的步数记为n）：
# 技术栈：Python 3.9+
# 计算归并排序的工作量（模拟）
def merge_sort_work(n):
# 边界条件：n<=1时工作量为1
if n <= 1:
return 1
# 递推式：2*T(n/2) + n
return 2 * merge_sort_work(n // 2) + n
# 测试n=4（log2(4)=2，所以结果应该是4*2=8）
print(merge_sort_work(4)) # 输出8，符合推导
# 测试n=8（log2(8)=3，结果应该是8*3=24）
print(merge_sort_work(8)) # 输出24，验证正确
三、主定理的常见误区：别踩这些坑
主定理虽然好用，但很多人用的时候会出错，要么是递推式不符合标准形式，要么是参数代错，要么是忽略正则条件。下面说几个最容易踩的坑：
3.1 误区1：递推式不符合主定理的标准形式，硬套
主定理只适用于T(n)=a*T(n/b)+f(n)的形式，也就是每次递归的问题规模都是n/b，而且递归次数是固定的a。如果你的递归不是这样，就不能套主定理。
最典型的例子是快速排序的最坏情况。快速排序的逻辑是选一个基准数，把数组分成比基准小的和比基准大的两部分，然后递归排序这两部分。如果每次选的基准数都是数组里最小的（比如数组已经有序，每次选第一个数当基准），那拆分后的两部分，一个长度是0，一个长度是n-1。这时候递推式是T(n)=T(n-1)+n，这个式子的b不是固定的（每次问题规模是n-1，不是n/b），所以不符合主定理的标准形式，不能套主定理。
那快速排序最坏情况的时间复杂度怎么算？还是用展开法： T(n) = T(n-1) + n T(n-1) = T(n-2) + (n-1) ... T(1) = 1 把所有式子加起来，T(n) = 1 + 2 + ... + n = n(n+1)/2，所以时间复杂度是O(n²)。
3.2 误区2：参数代错，尤其是a和b的意思搞反
很多人会把a和b搞反，比如二分查找的递推式是T(n)=1*T(n/2)+1，a是递归次数（1次），b是问题规模缩小的倍数（2倍），但有人会把a写成2，b写成1，这样log_b(a)就会算错，导致时间复杂度错。
再举个例子：假设一个递归每次把问题规模砍成1/3，调用3次，那a=3，b=3，log_b(a)=1，要是把a写成3，b写成3是对的，但如果写成a=3，b=1，那log_b(a)就没意义了（因为b要大于1）。
3.3 误区3：情况3忽略正则条件，直接套结论
主定理的情况3有个“正则条件”，很多人会忽略，以为只要f(n)增长比a*T(n/b)快，就能套结论。其实如果不满足正则条件，时间复杂度就不是O(f(n))。
举个反例：递推式T(n)=2T(n/2)+nlogn。这里a=2，b=2，log_b(a)=1，n^(log_b(a))=n，f(n)=nlogn，f(n)的增长比n快很多，但它不满足正则条件。因为af(n/b)=2*(n/2 * log(n/2))=n*(logn - 1)，而cf(n)=cnlogn，不管c取多少小于1的数，当n很大的时候，n(logn - 1) 都会比cnlogn大，所以不满足af(n/b) ≤ cf(n)。这时候主定理的情况3不适用，需要用其他方法推导，这个递推式的时间复杂度是O(n*(logn)²)。
四、递归时间复杂度的应用场景和注意事项
4.1 应用场景
递归时间复杂度的推导，主要用于分治算法的分析，比如：
- 搜索类：二分查找、二叉树的遍历（前序、中序、后序）
- 排序类：归并排序、快速排序（平均情况）
- 分治类：快速幂、矩阵乘法（Strassen算法）、FFT（快速傅里叶变换）
- 动态规划：有些递归实现的动态规划（比如斐波那契数列的递归实现）
4.2 技术优缺点
优点
- 主定理标准化了递推式的计算，不用每次手动展开，节省时间
- 推导结果可以直观反映算法的增长趋势，帮助判断算法的效率（比如O(nlogn)的算法比O(n²)的快）
- 可以用来优化算法：比如如果推导出来的时间复杂度不符合预期，就可以调整递归的拆分方式（比如快速排序选基准数的方法，避免最坏情况）
缺点
- 主定理只适用于标准形式的递推式，复杂的递归（比如随机拆分的、问题规模不固定的）不适用
- 推导过程需要对递推式的参数有清晰的理解，容易因为参数代错导致结果错误
- 时间复杂度是“最坏情况”或“平均情况”的近似，不能完全代表实际运行时间（比如常数项、缓存等因素会影响实际速度）
4.3 注意事项
- 写递归代码的时候，要先明确递推式的参数（a、b、f(n)），再推导时间复杂度，不要先写代码再瞎套公式
- 遇到不满足主定理的递推式，要回到展开法或其他方法（比如递归树法）推导，不要硬套
- 时间复杂度的推导结果要和实际测试结合，比如有些算法理论上时间复杂度低，但实际因为常数项大，反而比复杂度高的算法慢（比如归并排序和快速排序，快速排序的常数项小，实际运行更快）
五、总结
递归算法的时间复杂度推导，核心是先把算法的工作量拆解成递推式，再通过展开法或主定理计算时间复杂度。主定理是个好用的工具，但要注意它的适用条件和常见误区。
回顾一下整个流程：
- 理解递归的工作量，写出递推式（T(n) = a*T(n/b) + f(n)）
- 分析递推式的参数（a、b、f(n)）
- 符合主定理的标准形式，就套三个情况得出时间复杂度；不符合就用展开法
- 避免常见误区：递推式不标准别硬套、参数别代错、情况3别忽略正则条件
只要掌握了这个流程，递归的时间复杂度推导就不再是难题，反而会成为你分析算法、优化算法的有力工具。
评论
围绕“递归算法的时间复杂度推导不再困难：从递推关系式到主定理的实战应用与常见误区”参与讨论