递归函数时间复杂度为何是O(2^n)而非O(n*2^n)？

你推导时踩了两个非常典型的递归复杂度计算误区，直接导致结果偏差：

• 误区1：混淆了递归树单层节点数和总节点数的概念
  你提到“每一层的节点数为2^n”，这个2^n实际是整棵递归树的总节点数量级，根本不是单一层的节点数。
  我们可以直接拆解递归树的结构验证：
  最顶层是初始调用dib(n)，记为第0层，节点数是2^0 = 1；
  第1层是顶层调用触发的2个dib(n-1)调用，每个上层节点会生成2个下层调用，总节点数为2^1 = 2；
  第2层是每个第1层节点各自触发的2个dib(n-2)调用，总节点数为2^2 = 4；
  以此类推，第k层的所有调用都是dib(n-k)，该层总节点数固定为2^k；
  直到递归触达终止条件n<=1，也就是n-k=1时，k = n-1，这最后一层的节点数为2^(n-1)。
  把所有层的节点数加总，就是公比为2的等比数列求和：2^0 + 2^1 + 2^2 + ... + 2^(n-1) = 2^n - 1，量级正好是O(2^n)。你测试时统计到的约32个节点，对应输入n=5的场景，代入公式得到2^5-1=31，和实际统计结果完全吻合。
• 误区2：错误给总复杂度额外乘了递归树高度
  你判断递归树高度为n是正确的，但你错误地用树高n去乘了你误以为的“每层2^{n个节点”。实际上对于公比大于1的等比数列求和，总和的量级和最后一项的量级是相等的——前面所有层的节点数加总，都不会超过最后一层的节点数，根本不存在“n层每层2}n个节点、总和要乘n”的逻辑。

额外参考 #

什么时候这类双递归的时间复杂度会是O(n*2^n)？当每个递归节点内部，除了两次递归调用之外，还要执行O(n)量级的操作时——比如每个函数入口要跑一个长度为n的循环做计算，这时候总时间复杂度才是总节点数乘单节点操作复杂度，得到O(n*2^n)。你给出的dib函数除了两次递归调用外没有其他额外操作，每个节点的执行时间是常数级O(1)，总时间复杂度自然等于总节点数的量级O(2^n)。

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