求解下述递归函数的时间复杂度，验证递推式T(n)=T(n-1)+n是否正确

你的递推式推导是错误的，我们来重新分析这个函数的执行逻辑：

代码执行流程 #

函数test2(n)的逻辑如下：

• 当n<=0时，直接返回0，时间复杂度为O(1)
• 当n>0时，执行一个外层循环（i从0到n，共n+1次迭代）：
  • 每次迭代中，先执行内层循环（j从0到n，共n+1次），这部分的时间开销是O(n)（内层循环做n+1次打印操作，属于线性时间）
  • 然后递归调用test2(n-1)

正确的递推式 #

基于上述流程，时间复杂度的递推式应该是：

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

其中：

• (n+1)*T(n-1)：对应n+1次递归调用test2(n-1)的总开销
• (n+1)*n：对应n+1次外层迭代中，每次内层循环的总开销（精确表达式是(n+1)*(n+1)，渐进分析中可简化为n(n+1)）

时间复杂度推导 #

我们通过展开递推式分析：

1. 代入T(n-1) = n*T(n-2) + n*(n-1)到递推式中：

   T(n) = (n+1)*[n*T(n-2) + n*(n-1)] + n(n+1)
   = (n+1)*n*T(n-2) + (n+1)*n*(n-1) + n(n+1)
   

2. 继续展开直到T(0)（T(0)=0），最终第一项会因T(0)=0消失，剩下的求和项可简化为：

   T(n) = (n+1)! * sum_{m=0}^{n-1} 1/m!
   

   其中sum_{m=0}^{n-1} 1/m!是自然常数e的部分和，当n增大时趋近于e（约2.718），属于常数级。

因此，T(n)的时间复杂度是O(n!)（阶乘级），远大于你之前推导的O(n²)。

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