分析递归函数A(n)的时间复杂度 #

嘿，这个问题确实很容易让人绕进去——递归的分支效应加上循环的线性开销，很容易把两种复杂度分析的直觉混在一起。咱们一步步拆解清楚：

定义时间复杂度函数 #

首先，我们设T(n)为计算A(n)所需的时间开销。根据函数定义：

• 当n ≤ 10时，T(n) = O(1)，因为直接返回结果，没有循环和递归调用。
• 当n > 10时，函数先执行一个从1到n的循环（开销O(n)），然后调用A(n/3)、A(n/6)、A(n/4)，所以递归式为：

  T(n) = O(n) + T(n/3) + T(n/6) + T(n/4)
  

用递归树分析复杂度 #

现在我们用递归树来直观分析这个式子：

1. 递归树的第一层（根节点）开销是n（就是那个循环的开销）。
2. 第二层有3个节点，各自的开销分别是n/3、n/6、n/4，总和是：

   n*(1/3 + 1/6 + 1/4) = n*(4/12 + 2/12 + 3/12) = 9n/12 = 3n/4
   

3. 第三层是每个第二层节点再分出3个子节点，计算下来第三层的总开销是(3n/4)*(3/4) = (3/4)²n。
4. 以此类推，第k层的总开销是(3/4)^k * n。

递归树的深度是O(log n)——因为每次递归调用的参数至少除以3，所以深度是log₃n，属于对数级。

把所有层的开销加起来，这是一个首项为n、公比为3/4（小于1）的等比数列：

总开销 = n + (3/4)n + (3/4)²n + ... + (3/4)^(log n) * n

根据等比数列求和公式，总和为：

总开销 = n*(1 - (3/4)^log n)/(1 - 3/4) = 4n*(1 - o(1))

这里(3/4)^log n会随着n增大趋近于0（因为log(3/4)是负数，等价于n^log(3/4)），因此总开销是O(n)。

解答你的困惑 #

1. 为什么不是O(n log n)？你可能误以为每个递归分支的深度是log n，直接用n乘以log n。但实际上，递归树每一层的总开销按等比数列递减，后续层的开销总和不会超过n的常数倍，所以整体是线性复杂度，而非线性对数级。
2. 为什么不会是指数级？指数级复杂度通常出现在递归分支的扩张速度超过参数缩小速度时（比如T(n)=2T(n-1)+O(1)，每个调用产生2个新调用，参数仅减1）。但在这里，每一层的总开销以3/4的比例缩小，没有扩张趋势，因此绝对不会出现指数级增长。

代入法验证 #

假设T(n) ≤ C*n（C是常数），代入递归式：

T(n) ≤ n + C*(n/3 + n/6 + n/4) = n + C*(9n/12) = n + C*(3n/4)

只要取C ≥ 4，就有n + 3Cn/4 ≤ Cn（因为n ≤ Cn/4当C≥4时成立），证明T(n)=O(n)的假设成立。

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