为何计算斐波那契数时记忆化（memoization）耗时近乎恒定，与动态规划差异显著？

先看我们实现的两种斐波那契数计算代码：

def fibo_memo(i, memo={}):
    if i <= 0:
        return 0
    elif i == 1:
        return 1
    elif i in memo:
        return memo[i]
    else:
        memo[i] = fibo_memo(i-2, memo) + fibo_memo(i-1, memo)
        return memo[i]

def fibo_dp(i):
    if i <= 0:
        return 0
    elif i == 1:
        return 1

    dp = [0] * (i + 1)
    dp[1] = 1

    for j in range(2, i + 1):
        dp[j] = dp[j-1] + dp[j-2]

    return dp[i]

assert(fibo_memo(100) == fibo_dp(100))

对应的性能测试结果：

i = 10
%timeit fibo_memo(i)  # 73 ns
%timeit fibo_dp(i)  # 309 ns

i = 100
%timeit fibo_memo(i)  # 73 ns
%timeit fibo_dp(i)  # 2.54 微秒

i = 1000
%timeit fibo_memo(i)  # 73 ns
%timeit fibo_dp(i)  # 33 微秒

核心差异分析 #

• 记忆化版本的持久缓存特性：
  fibo_memo的memo参数用了默认空字典，而Python里函数的默认参数是在函数定义时就创建的，并非每次调用都重建。第一次调用时，递归计算出的所有斐波那契值都会存入这个全局唯一的memo字典；之后无论传入多大的i，只要该值已存在于memo中，就直接返回缓存结果——这是O(1)的字典查找操作，所以耗时几乎恒定。

  哪怕先调用fibo_memo(1000)再调用fibo_memo(10)，耗时也不会有明显变化，因为所有值都已经提前缓存完毕。

• 动态规划版本的全量重计算逻辑：
  fibo_dp每次调用都会从头执行完整流程：创建长度为i+1的数组，再从j=2循环到j=i逐个计算值。这个过程的时间复杂度是O(n)，i越大，数组长度越长、循环次数越多，耗时自然线性增长，和测试结果完全匹配。

额外验证点 #

如果想让记忆化版本的耗时随i变化，可以每次调用手动传入空字典（比如fibo_memo(100, {})），这时它会重新递归计算所有值，耗时就会和i正相关。

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