为何斐波那契记忆化算法传与不传memo字典时间复杂度无差异？

你疑惑的核心原因是对Python默认参数的机制理解有误——Python的函数默认参数是在函数定义时初始化的，而不是每次调用函数时重新创建。

关键细节拆解 #

• 默认参数的创建时机：当你写下def fib(n , memo = {}):这行代码时，Python就已经创建了一个空字典对象，并把它绑定为memo的默认值。之后每次调用fib如果没传memo参数，都会复用这个已经存在的字典，而不是新建一个。
• 不传memo的递归调用逻辑：在第一种写法里，fib(n-1)没有传memo，所以递归调用会直接使用默认的那个字典——这个字典和外层函数里的memo是同一个对象（内存地址相同）。也就是说，所有递归调用都在共享同一个缓存字典，自然能实现记忆化，时间复杂度和显式传memo的版本完全一致。

两种写法的本质对比 #

两种写法在仅使用默认参数调用的场景下，行为完全等价：

• 不传memo的代码：

def fib(n , memo = {}):
    if(n<=2): return 1
    if(n in memo): return memo[n]
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

• 传memo的代码：

def fib(n , memo = {}):
    if(n<=2): return 1
    if(n in memo): return memo[n]
    memo[n] = fib(n-1 , memo) + fib(n-2 , memo)
    return memo[n]

唯一的差异出现在显式传入自定义字典的场景：第二种写法会把你传入的字典传递给所有递归调用，而第一种写法的递归调用依然会使用默认的全局字典。但在你的测试场景中，两者没有区别。

验证小技巧 #

你可以在调用fib(5)之后，打印函数的默认参数看看：

print(fib.__defaults__)

输出会是({3: 2, 4: 3, 5: 5},)，这直接证明了默认字典在多次调用中被复用且修改了。

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