遞歸斐波那契算法的複雜性和步數

我有一個任務是對遞歸斐波那契算法進行分析。該算法具有O（2^n）複雜度。我已經讀過n是深度，在另一篇文章中，n是2^n中的輸入大小。那麼真相是什麼？然後如何統計步數（也許我們也可以稱之爲遞歸調用）來獲得一個斐波那契數。我有這樣的代碼：遞歸斐波那契算法的複雜性和步數

#include <bits/stdc++.h> 

using namespace std; 

long fibonacci(long); 

long jl=0; 
double rt; 

int main(){ 
    long result, number; 

    scanf("%ld", &number); 
    clock_t mulai = clock(); 
    result = fibonacci(number); 
    rt = ((double) (clock() - mulai))/CLOCKS_PER_SEC; 
    printf("Fibonacci (%ld) = %ld\n", number, result); 
    printf("Jumlah langkah = %ld\n", jl); 
    printf("Running Time = %.10f\n", rt); 
    return 0; 
} 

long fibonacci(long n){ 
    jl++; 
    if(n==0 || n==1) 
     return n; 
    else 
     return fibonacci(n-1) + fibonacci(n-2); 
}

jl在此代碼中的步數（遞歸調用）。這是我的計算示例：

F（1），JL = 1

F（2），JL = 3

F（3），JL = 5

F（5），jl = 15

那麼，這是真的還是假的？如果錯誤什麼是正確的代碼？謝謝。

來源

2017-01-01 RiefSapthana

你的問題確實不清楚。你想知道'n'是什麼嗎？分析代碼的複雜性時你有問題嗎？你是否試圖計算代碼運行的次數？考慮修改問題更清楚。 – nitzanms

我想了解n是什麼，以及如何計算步數/遞歸調用 – RiefSapthana

在複雜性分析中，'n'總是輸入的大小。遞歸深度是你從'n'計算來確定複雜度的東西。 – Barmar

這裏的想法是，如果你要求例如fibonacci(3)你將需要做一些遞歸調用。爲了形象化，我們可以畫一棵樹，fibonacci(3)調用fibonacci(3 - 1)和fibonacci(3 - 2)等

  fibonacci(3) 
      / \ 
     fibonacci(2) fibonacci(1) 
    / \ 
fibonacci(0) fibonacci(1)

，如果你需要計算fibonacci(4)樹變得

     fibonacci(4) 
        /   \ 
      fibonacci(3)   fibonacci(2) 
      / \    |   \ 
     fibonacci(2) fibonacci(1) fibonacci(1) fibonacci(0) 
    / \ 
fibonacci(0) fibonacci(1)

你或許可以發現的模式已經在其最深點，樹的深度爲n。而節點的數量是O（2^n）。

也就是說，如果你正在執行這個函數，你最多隻能遞減n個級別，但仍然執行〜2^n個函數調用。

來源

2017-01-01 20:52:03

ps因爲我看到'clock（）'等等，所以我們討論的是理論時間複雜度，而不是實際時間。這個想法是，當n變大時，fibonacci（n）需要完成的時間呈指數增長。 –

遞歸斐波那契算法的複雜性和步數

回答

相關問題