分析複雜的代碼（斐波納契數列）

-3

def fib_iterative(n): 
    if n == 0: 
     return [] 
    if n == 1: 
     return [1] 
    if n == 2: 
     return [1,1] 
    fib_list = [1,1] 
    for i in range(0,n): 
     fib_list.append(fib_list[i]+fib_list[i+1]) 
    return fib_list

這是遞歸版本：

def fib_recursive(n): 
    if n == 1: 
     return 1 
    elif n == 2: 
     return 1 
    else: 
     return fib_recursive(n-1) + fib_recursive(n-2) 

def fib_numbers_in_list(n): 
    fibn = [] 
    for x in range(1,n+1): 
     fibn.append(fib_recursive(x)) 
    return fibn

什麼是大-O每？

調用函數是fib_numbers_in_list（n）和fib_iterative（n）返回列表中的前n個斐波那契數。

有沒有一種方法可以找到O（log n）算法來生成n個斐波納契數？

來源

2016-11-30 Umair Qazi

你應該自己解決這個問題。 SO不是解決別人的任務。 –

在第二個例子中我看不到任何遞歸，它看起來有點*困惑*。。。 –

這是我寫的代碼。我只是有點困惑，當我運行n = 50的第二個版本時，python解釋器暫停。而第一個版本：它提供了輸出儘快。只想在Big-O上留下一些想法 @NeilSlater在第二個版本中，使用遞歸計算第n個斐波那契數，然後第二個函數按順序將它們追加到列表中。 –

你可以看看這裏各種蟒蛇行動的大O表示法來估計時間複雜度： TimeComplexity

而且這裏有一個例子：

example

來源

2016-11-30 08:26:35 Inconnu

def fib_iterative(n): 
    if n == 0: 
     return [] 
    if n == 1: 
     return [1] 
    if n == 2: 
     return [1,1] 
    fib_list = [1,1] 
    for i in range(0,n): 
     fib_list.append(fib_list[i]+fib_list[i+1]) 
    return fib_list

這個函數有一個for-loop，它重複n次。這使得功能O(n)時間複雜。

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

def fib_numbers_in_list(n): 
    fibn = [] 
    for x in range(1,n+1): 
     fibn.append(fib_recursive(x)) 
    return fibn

我認爲這是一個錯誤調用代碼fib(n-1) + fib(n-2)。我認爲這應該是fib_recursive(n-1) + fib_recursive(n-1)。

我們假設fib_recursive(n)有f(n)計算要做。簡單的方程來估計它將是f(n) = f(n-1) + f(n-2)。邊界條件是f(2) = 1, f(1) = 1。這對你很熟悉了嗎？遞歸代碼的時間複雜度最終將與輸入n的斐波那契數相同。

就像你可能已經知道的那樣，第n個斐波納契數是正比於(2.736) ** n。這使得遞歸函數的時間複雜度爲O(2.736 ** n)。（如果你想了解更多信息，請訪問http://mathworld.wolfram.com/FibonacciNumber.html）

嗯，我們還沒有完成。我們必須乘以n，因爲您想知道所有斐波納契數從1到n。所以慷慨的計算會使答案O(n * 2.736 ** n)

來源

2016-11-30 09:38:29

分析複雜的代碼（斐波納契數列）

回答

相關問題