为何这段代码的时间复杂度为2ⁿ而非N×2ⁿ？需计入fib的N次调用

代码示例 #

def allFib(n):
 for i in range(n):
   print(str(i) + ":, "+ str(fib(i)))

def fib(n):
  if n<=0:
    return 0 
  elif n == 1:
    return 1 
  return fib(n-1) + fib(n-2)

用户疑问 #

该代码的时间复杂度为何被认定为2ⁿ，而非N×2ⁿ？难道不应该将fib函数被调用N次这一情况纳入考量吗？

解答 #

要搞清楚这个问题，核心是理解渐进时间复杂度只关注n趋向无穷大时的主导项，具体拆解如下：

• 先明确单个fib(k)的时间复杂度：
  递归版fib(k)的调用次数是O(2ᵏ)，因为每一层递归都会分裂为两个子调用，整体调用次数呈指数级增长，近似为2的k次方。

• 计算allFib(n)的总调用次数：
  allFib(n)会依次调用fib(0)到fib(n-1)，总调用次数是这些单个fib(k)调用次数的总和，也就是：
  O(2⁰) + O(2¹) + O(2²) + ... + O(2ⁿ⁻¹)
  这是一个等比数列求和，结果为O(2ⁿ - 1)，当n足够大时，常数项可以忽略，因此最终是O(2ⁿ)。

• 为什么不是O(n×2ⁿ)？
  你可能误以为每个fib(i)的复杂度都是O(2ⁿ)，但实际上fib(i)的复杂度是O(2ⁱ)，只有fib(n-1)的复杂度接近O(2ⁿ)，前面所有小i对应的fib(i)调用次数加起来，总和远小于fib(n-1)的调用次数。比如n=20时，总和约为2×2²⁰，常数系数在渐进复杂度中会被忽略，所以不会是O(n×2ⁿ)。

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