什麼是這個程序的大O複雜性...我得到O（2^n），但我無法找到正確的答案

Question

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

n = int(input()) 
for val in range(n): 
    print(fib(val)) 

#I做了一些計算，得到O（n^2），但我不知道正確的答案

Answer 1

不同的參數：

你的算法遞歸，直到它「觸底」，在fib(1)返回1.

所以，你這樣做（斐波那契數）調用得到斐波那契並添加1。

所以fib(n)是O(fib(n))。

比奈的斐波那契數公式可以寫成fib(n) == int(0.5 + (phi ** n)/(5 ** 0.5))其中phi是黃金比例，1.6180339 ......

剝離常數，你會得到O(phi ** n)這就減少了O(2 ** n)。

現在，fib(n)實際上比O(fib(n))多一點點，因爲你也會對fib(0)進行一堆調用，它返回0--因此它增加了調用次數而不是總和。

事實證明，計算fib(n)時，你讓fib(n - 1)調用fib(0)（挑戰：編寫一個函數來證明這一點！）。

所以fib(n)實際上是O(fib(n) + fib(n - 1))是O(fib(n + 1))這是O(phi ** (n + 1))，仍然減少了O(2 ** n)。