递归函数时间复杂度2^n-1推导疑问：以fn(n)为例

首先明确，你给出的是无缓存的递归斐波那契实现，我们先定义C(n)为计算fn(n)时的总函数调用次数，接下来一步步推导时间复杂度的由来：

推导过程 #

1. 基础情况定义：

   • 当n < 0时，C(n) = 1（调用一次直接返回0）
   • 当n = 0时，C(0) = 1（调用一次返回0）
   • 当n = 1时，C(1) = 1（调用一次返回1）

2. 递归关系建立：
   计算fn(n)时，会先发起fn(n-1)和fn(n-2)两次子调用，再加上自身这一次调用，因此总调用次数的递归公式为：

   C(n) = 1 + C(n-1) + C(n-2)
   

3. 递推与上界验证：
   我们可以先展开几个值看规律：

   • C(2) = 1 + C(1) + C(0) = 1+1+1=3
   • C(3) = 1 + C(2) + C(1) =1+3+1=5
   • C(4)=1+C(3)+C(2)=1+5+3=9
   • C(5)=1+C(4)+C(3)=1+9+5=15

   你提到的2^n -1是该函数调用次数的上界，而非精确值。我们可以用数学归纳法证明C(n) ≤ 2^n -1：

   • 基础验证：n=1时，1 ≤ 2^1-1=1；n=2时，3 ≤ 2^2-1=3，均成立。
   • 归纳假设：若对所有k ≤n，C(k) ≤2^k -1成立，则：
     C(n+1)=1+C(n)+C(n-1) ≤1+(2^n -1)+(2^(n-1)-1) = 3*2^(n-1)-1 ≤ 2^(n+1)-1（因为3*2^(n-1) ≤ 2*2^n=2^(n+1)）

   因此，C(n)的增长不会超过2^n -1，我们用**渐进时间复杂度O(2^n)**来描述这个递归实现的效率——它能准确反映该算法指数级增长的低效特性。

实际调用次数与上界的差异 #

你观察到n=4时实际调用9次，而2^4-1=15，这是因为2^n-1是最坏情况的理论上界：当递归到n<2时就会终止，不会像完全二叉树一样持续分裂出子节点。但随着n增大，实际调用次数与2^n的比例会趋近于一个常数，所以用O(2^n)作为时间复杂度的描述依然合理。

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