递归调用的乘法是否影响主定理应用？求递归函数复杂度

核心结论 #

你的递推式写法T(n) = 3T(n/9) + O(n)是正确的，递归调用的乘法运算不会改变子问题的调用次数，a=3的取值没问题，最终时间复杂度为Θ(n)。

详细推导 #

1. 拆解时间开销

   • 当n≥2时，函数先执行一个for循环：从i=1到i<n执行c++，这部分执行了n-1次操作，时间复杂度为O(n)。
   • 递归调用部分：代码中4 * T2(n/9) * T2(n/9)需要连续调用两次T2(n/9)，再加上后面单独的T2(n/9)，总共是3次独立的递归调用，每次调用的规模都是n/9，因此这部分的时间开销是3*T(n/9)。
   • 剩下的乘法、加法操作都是常数时间，可忽略不计。

2. 递推式确立
   综合以上分析，时间复杂度的递推式为：

   T(n) = 3*T(n/9) + O(n) ，n≥2
   T(n) = O(1) ，n<2
   

3. 主定理求解
   对照主定理的标准形式T(n) = a*T(n/b) + f(n)：

   • a=3（子问题数量）
   • b=9（子问题规模的缩小比例）
   • f(n)=O(n)

   计算对数项：log_b a = log₉3 = 1/2。由于f(n)=O(n)的指数1大于1/2，且满足主定理第三类的正则条件（存在常数c=0.75<1，使得3*f(n/9)=3*(n/9)=n/3 ≤ 0.75n=c*f(n)），因此时间复杂度为Θ(n)。

4. 乘法误区澄清
   递归调用后的乘法只是对返回值的运算，不会增加函数调用的次数。不管返回值是用来乘还是加，只要是一次函数调用，就对应一次T(n/9)的时间开销，这里确实是3次独立调用，所以a=3的取值完全正确。

内容的提问来源于stack exchange，提问作者Nom