☰

フィボナッチ数列の計算の複雑さ 質問する

tag-icon • tag-icon time-complexity big-o complexity-theory fibonacci
フィボナッチ数列の計算の複雑さ 質問する

私は Big-O 表記法を理解していますが、多くの関数でそれを計算する方法がわかりません。特に、フィボナッチ数列の単純なバージョンの計算の複雑さを理解しようとしています。

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

フィボナッチ数列の計算複雑さはどのくらいですか、またそれはどのように計算されますか?

ベストアンサー1

計算する時間関数は、Fib(n)計算時間Fib(n-1)と計算時間Fib(n-2)とそれらを加算する時間の合計 ( ) としてモデル化します。これは、同じものを繰り返し評価すると同じ時間がかかる、つまりメモ化が使用されない、とO(1)想定しています。Fib(n)

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

この再帰関係を（たとえば生成関数を使用して）解くと、答えが得られます。

あるいは、深さのある再帰ツリーを描いて、nこの関数が漸近的であることを直感的に理解することもできます。その後、帰納法によって推測を証明できます。O(2n)

ベース：n = 1明らかです

と仮定すると、T(n-1) = O(2n-1)

T(n) = T(n-1) + T(n-2) + O(1) これは次の式に等しい

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

しかし、コメントにもあるように、これは厳密な境界ではありません。この関数の興味深い点は、T(n)は漸近的にの値と同じでFib(n)あるということです。なぜなら、両方とも次のように定義されるからです。

f(n) = f(n-1) + f(n-2)。

再帰ツリーの葉は常に 1 を返します。 の値は、Fib(n)再帰ツリーの葉によって返されるすべての値の合計であり、葉の数に等しくなります。各葉の計算には O(1) かかるため、T(n)は に等しくなりますFib(n) x O(1)。したがって、この関数の厳密な境界はフィボナッチ数列自体 (~ ) です。この厳密な境界は、上で述べたように生成関数を使用して見つけることができます。θ(1.6n)

おすすめ記事