3

時間計算量を計算するための再帰方程式を見つけたい

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

再帰方程式は解けますが、方程式と基本ケースを見つけるのが困難です。

これは正しい方程式ですか？

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

ベースケースの場合は？

T(0)=0

T(1)=0

また、一般的に、アルゴリズムの基本ケースはどのように見つけることができますか?

4

1 に答える 1

3

複雑さのために、この例の基本ケースは通常重要ではありません。個人的には、何も時間がかからないことに基づいて、おそらくT(0) = 1,を設定します。T(1) = 1しかし、あなたの再帰関係を見てください。それ自体がフィボナッチ スタイルの数列であり、ベース ケースに関係なく (ほぼ) 指数関数的になります。

基本ケースの一般的な問題は、具体的な答え (「計算にかかる時間はFib(0)?」) が必要なことですが、複雑さの計算における実際の「時間の単位」は通常、あまり定義されていません。正確には、 T(0) を定数 k_1に等しく、 T(1) を定数 k_2に等しく定義し、そこから作業する必要があります。再帰関係を解くために定数の数値が必要な場合は、おそらく何かが間違っています。

同様に、繰り返し関係を に設定できますT(n) = T(n-1) + T(n-2) + k_3。

複雑さの計算の「時間の単位」が「加算の実行回数」である場合、他のロジックを無視すると、基本ケースは で正しいことに注意してください0。これは、たとえば、パフォーマンスが分析の範囲外であるユーザー提供の関数によって加算が行われた場合に、時間を分析するのに便利な方法です。

于 2013-03-29T12:42:18.770 に答える