您可以將計算斐波那契數列的程式最佳化到什麼程度？

介紹

我學Python的時候，老師給我們佈置了一個作業－計算斐波那契數列的第N個數。

我覺得很簡單，所以我寫了這段程式碼：

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

後來我知道這種解決方案太花時間了。

優化程式

我將解決方案更改為迭代。

def fib(n):
    ls = [1,1]
    for i in range(2,n):
        ls.append(ls[i-1] ls[i-2])

    return ls[n-1]

我用matplotlib繪製它花費的時間：

import time
import matplotlib.pyplot as plt


def bench_mark(func, *args):
    # calculate the time
    start = time.perf_counter()
    result = func(*args)
    end = time.perf_counter()

    return end - start, result  # return the time and the result

def fib(n):
    ls = [1,1]
    for i in range(2,n):
        ls.append(ls[i-1] ls[i-2])

    return ls[n-1]

mark_list = []

for i in range(1,10000):
    mark = bench_mark(fib,i)
    mark_list.append(mark[0])
    print(f"size : {i} , time : {mark[0]}")

plt.plot(range(1, 10000), mark_list)
plt.xlabel('Input Size')
plt.ylabel('Execution Time (seconds)')
plt.title('Test fot fibonacci')
plt.grid(True)
plt.show()

結果在這裡：

花費的時間很短。

但是我寫了 fib(300000)，花了 5.719049899998936 秒。它太長了。

長大後，我學會了CACHE，所以我改變解決方案，使用dict來儲存結果。

from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n 



或者我們可以自己寫CACHE。 


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