如何计算递归函数的时间复杂度？附代码及推导疑问

首先看你给出的递归函数代码（修正了语法错误，比如判断相等应该用==，循环条件里的2^n在代码中通常用位运算1 << n或幂函数实现）：

Code(n) {
    if (n == 0) {
        print 1;
    } else {
        for (int i = 1; i < (1 << n); i++) {
            Code(n-1);
        }
    }
}

你的推导问题点 #

你写的递归式T(n)=O(2^n)+T(n-1)*2^(n-1)+O(1)存在一处关键错误：for循环的执行次数是2^n - 1次（i从1到2^n - 1），而非2^(n-1)次，因此递归调用的总时间是(2^n - 1)*T(n-1)，不是2^(n-1)*T(n-1)。

正确推导过程 #

我们用T(n)表示Code(n)的执行时间：

1. 基准情况：当n=0时，仅执行一次打印操作，时间为常数，即T(0) = O(1)。
2. 递归情况：当n>0时：
   • 循环本身的迭代开销（初始化i、判断条件、i自增）是O(2^n)（因为循环次数是2^n - 1，低阶项可忽略）；
   • 每次循环调用一次Code(n-1)，总递归调用时间为(2^n - 1)*T(n-1)；
   • 因此递归式为：

     T(n) = (2^n - 1)*T(n-1) + O(2^n) ，n>0
     T(0) = O(1)
     

接下来展开递归式分析增长速度：

• 把递归式展开到基准情况，会得到一个乘积项和求和项的组合：
  T(n) = [Π_{k=1}^n (2^k - 1)] * T(0) + c*Σ_{k=1}^n [2^k * Π_{m=k+1}^n (2^m -1)]（c为常数）
• 其中乘积项Π_{k=1}^n (2^k -1)的增长速度是Θ(2^{n²/2})：因为Π_{k=1}^n 2^k = 2^{1+2+...+n} = 2^{n(n+1)/2}，而2^k -1和2^k是同阶的，所以乘积项的量级是2^{n²/2}；
• 求和项的最大项就是乘积项本身，因此求和项也属于O(2^{n²/2})；
• 最终T(n)的时间复杂度为O(2^{n²})（因为2^{n²/2}和2^{n²}是同阶的，底数为大于1的常数时，指数同阶则复杂度同阶）。

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