再帰的なフィボナッチの複雑さとステップ数

Question

私は、再帰的なフィボナッチアルゴリズムについての分析を行う作業があります。アルゴリズムは、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

だから、それは真か偽ですか？ falseの場合、正しいコードは何ですか？ありがとうございました。

Answer 1

ここで考えているのは、インスタンスfibonacci(3)を求める場合、再帰呼び出しを行う必要があるということです。あなたはfibonacci(4)ツリーはおそらく、その最深点で、すでにパターンを見つけることができ

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

なっ計算する必要がある場合、我々は木、fibonacci(3)通話fibonacci(3 - 1)とfibonacci(3 - 2)など

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

を描くことができます可視化するために、木は深さnを有する。一方、ノード数はO（2^n）です。

つまり、この関数を実行している場合は、最大でnレベルまで再帰しますが、依然として〜2^n個の関数呼び出しを実行します。