斐波那契快速递归程序的复杂性
Complexity of Fibonacci Fast Recursive Program
def fastfib(n, fib_dict = {0: 1, 1: 1}):
if n not in fib_dict:
fib_dict[n] = fastfib(n-1, fib_dict) + fastfib(n-2, fib_dict)
return fib_dict[n]
我认为这里的复杂度是n^2，但我不确定。
由于您正在用 n 值填充字典，因此下限为 O(n)。但是，由于您只对每个 n 执行恒定时间操作（Python 字典查找操作是 O(1)，尽管已摊销） ，这个算法应该是O(n)（摊销）。这种在 table 中保存已计算值的技术称为 memoization.
def fastfib(n, fib_dict = {0: 1, 1: 1}):
if n not in fib_dict:
fib_dict[n] = fastfib(n-1, fib_dict) + fastfib(n-2, fib_dict)
return fib_dict[n]
我认为这里的复杂度是n^2，但我不确定。
由于您正在用 n 值填充字典，因此下限为 O(n)。但是，由于您只对每个 n 执行恒定时间操作（Python 字典查找操作是 O(1)，尽管已摊销） ，这个算法应该是O(n)（摊销）。这种在 table 中保存已计算值的技术称为 memoization.