求解含内部循环的递归卡特兰数代码的时间复杂度

嘿，你写的这段代码正好是卡特兰数的递归实现，咱们一步步拆解它的时间复杂度，从递推公式到渐近分析全给你掰明白。

第一步：写出时间复杂度的递推式 #

首先定义T(n)为计算Catalan(n)的总运行时间：

• 当n ≤ 1时，直接返回1，没有递归调用，所以T(0) = T(1) = O(1)（可以看作常数时间）。
• 当n > 1时，代码会执行一个n次的循环，每次循环调用两次递归：Catalan(i)和Catalan(n-i-1)，再加上循环本身的开销（比如变量i的递增、res的累加，总共是O(n)时间）。因此递推式为：

  T(n) = n + sum_{i=0}^{n-1} [T(i) + T(n-i-1)]
  

  注意到sum_{i=0}^{n-1} T(n-i-1)其实就是sum_{i=0}^{n-1} T(i)（只是求和顺序反过来），所以递推式可以简化为：

  T(n) = 2 * sum_{i=0}^{n-1} T(i) + O(n)
  

第二步：结合卡特兰数的渐近性质 #

卡特兰数本身的递推式是C(n) = sum_{i=0}^{n-1} C(i)*C(n-i-1)，其渐近公式为：

C(n) ~ 4^n / (n^(3/2) * sqrt(pi))

也就是C(n) = Theta(4^n / n^(3/2))。

对于咱们的递归实现，每次计算Catalan(n)都会重复计算所有子问题（没有记忆化），因此T(n)的增长速度和卡特兰数的累加和直接相关：

• 下界：T(n) = Omega(4^n / sqrt(n))，因为sum_{i=0}^{n-1} C(i)的增长速度是Theta(4^n / sqrt(n))，而T(n)至少是这个和的两倍加上线性项。
• 上界：T(n) = O(4^n / sqrt(n))，通过归纳假设可以证明，存在足够大的常数K，使得T(n) ≤ K*4^n / sqrt(n)对所有n成立。

结论 #

这段递归代码的时间复杂度是**Theta(4^n / sqrt(n))**，属于指数级增长——这也是为什么没有记忆化的卡特兰数递归实现效率极低的原因。如果要优化，推荐用动态规划（记忆化搜索或迭代递推）将时间复杂度降到O(n²)，甚至用通项公式优化到O(n)。

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