我的代码和显式使用 Memoization 的代码之间有区别吗？

Question

我尝试实现一个有效的函数来返回给定索引的斐波那契值。当我发现实现基本/简单递归函数来返回斐波那契数列的缺点时，我意识到随着不断重复计算，所需的计算时间开始呈指数级增长，以获取更大的 N 值，从而导致冗余。

但是，我后来发现有一种技术可以缓解问题......“Memoization”。基本上，我对它的作用的理解是，它缓存以前计算的值并将它们用于后续计算，从而减少任何冗余。

我很好奇哪种实现更有效 - 我的还是我在网上找到的。我知道运行代码所需的时间可能会有很小的差异，但是当 N 很大时，我的代码和另一个代码之间的差异似乎相当大。

这是我的代码：[06_fibo_dict.py]

import timeit

my_dict = {}

def fibonacci(n):
    """ To print the fibonacci series efficiently """
    if n == 1:
        x = 0
        my_dict[n] = x
        return x

    elif n == 2:
        fibonacci(1)
        x = 1
        my_dict[n] = x
        return x

    elif n == 3:
        fibonacci(2)
        x = 1
        my_dict[n] = x
        return x

    elif n > 3:
        fibonacci(n-1)
        x = my_dict[n-2] + my_dict[n-1]
        my_dict[n] = x
        return x

number = int(input("Enter N: "))

t = timeit.timeit(lambda: fibonacci(number), number=10)

fib = fibonacci(number)

print(f"Number: {fib}\n Time: {t:.32f}")

我的代码的输出：

$ python 06_fibo_dict.py
Enter N: 100
Number: 218922995834555169026
Time: 0.00059320009313523769378662109375


$ python 06_fibo_dict.py
Enter N: 200
Number: 173402521172797813159685037284371942044301
Time: 0.00105599989183247089385986328125

这是我在网上找到的代码：[07_fibo_memo.py]

import timeit

def fibonacci(n, cache={}):
    if n in cache:
        return cache[n]

    if n == 1:
        result = 0

    elif n == 2:
        result = 1

    else:
        result = fibonacci(n-1) + fibonacci(n-2)

    cache[n] = result
    return result

number = int(input("Enter N: "))

t = timeit.timeit(lambda: fibonacci(number), number=10)

fib = fibonacci(number)

print(f"Number: {fib}\n Time: {t:.32f}")

我在网上找到的代码的输出：

$ python 07_fibo_memo.py
Enter N: 100
Number: 218922995834555169026
Time: 0.00000469991937279701232910156250


$ python 07_fibo_memo.py
Enter N: 200
Number: 173402521172797813159685037284371942044301
Time: 0.00000709993764758110046386718750

Answer 1

因为你的代码一直递归到 0，当它在映射中已经具有较小的值时没有快捷方式，所以它做了不必要的工作。您在其他地方找到的版本只需要在第二次调用时完成从 700 到 500 的工作。