時間ボトムアップアプローチではフィボナッチ級数の複雑さ（DP）

Question

アルゴリズムをボトムアップ5については

はそれが8を呼び出し、このアルゴリズムはOの時間制限がありますどのように

a[0]=0,a[1]=1 
integer fibo(n) 
    if a[n]== null 
     a[n] = fibo(n-1) + fibo(n-2) 
    return a[n] 

（N）のアプローチで回。 pass of fibnacci series in Bottom Up approach

fibo（5）呼出しを上下に8回呼び出し、上から下に戻ります。総コールは私のビューの8 + 8 = 16です。時間の複雑さがどのようにO（N）であるかはわかりません。

私はここで多くの同様の質問に答えましたが、それらのすべては私の 関心とは関係ありません。 これらのいくつかは次のとおりです。

Time Complexity of Fibonacci Series

Time Complexity of Fibonacci Algorithm

誰も助けがappreciated.Thanks

Answer 1

になり、時間の複雑さについての質問に答える前に言及するために迅速なものがいくつかあります。この理由は、時間の複雑さがこれらの答えに少なくとも部分的に依存しているためです。

まず、基本条件（Fibbinacci番号0と1）とfibo関数で設定された配列mの配列があるので、プログラムにバグがあるようです再び使用されます。さらに重要なことに、n = 1またはn = 0に達すると、m [n]の値が返されます。アルゴリズムを次のように書き直したと仮定します。

a[0]=0,a[1]=1 
integer fibo(n) 
    if a[n]== null 
     a[n] = fibo(n-1) + fibo(n-2) 
    return a[n] 

いいえ、2番目の問題です。そのaは常に少なくともn + 1個の整数として定義されているとしましょう。入ってくるデータのための十分なスペースが必要です。これは、n + 1 ^番目のインデックスで値を上書きできるようにするため、重要です。範囲外ですが、間違っていますが、C++はそのような種類の保護を提供していません。そのような境界条件を検証することは、プログラマとしての責任です。 （私はC++とタグ付けされているので、C++と仮定しています。コードはPythonによく似ていますが、ラップアラウンドインデックスは独自の問題です。アルゴリズムの実行ごとに新しい配列 'a'を返します。すでに計算された値を格納する場合、それらの値を再評価する必要がないため、計算に時間を節約できるため、これは重要です。時間の複雑さをどのように計算するかに影響しない場合でも、時間の節約は素晴らしいことです。

素晴らしい。あなたの質問を始めましょう。下の画像を使って答えてみましょう。 nでアルゴリズムを開始すると、fibo（n-1）とfibo（n-2）の2つの再帰呼び出しが同時に発生することはありません。代わりにfibo（n-1）の最初の呼び出しが行われ、fibo（n-2）の2回目の呼び出しが開始される前に100％完了する必要があります。その呼び出しは、n ^番の番のラインからn-1 ^番のラインまでの緑色の線で表されます。

これらの緑色の線は、fibo（1）呼び出しに達するまで線の下の各再帰に適用されます。 a [n]がヌルではないため、その呼び出しは早期に終了します。最後に、fibo（0）の2番目の呼び出しが実行され、a [n]がnullではないため、早期に終了します。さて、再帰呼び出しの最初のセットについてはそうです。

各再帰呼び出しが戻ると、2番目の呼び出し（オレンジ色の破線で表されます）が作成されますが、[n]はnullではないため、呼び出しは早期に終了し、呼び出しは次のレイヤーに戻ります。

コールの数を数えます。 nから1まではn-1回帰呼び出しです。最後に、fibo（0）の呼び出しが1回追加され、n回の再帰呼び出しが行われます。その後、途中でn-2回の追加通話があり、早期に終了します。だから、私たちは2n-2の呼び出しを持っています。これはO（n）です。もちろん

あなたは（K + x）のFIBO、その後FIBO（k）を呼び出している場合、あなただけの最初の2倍を行う必要がありますすべてがFIBOから（k）のダウンは既に知られているので、呼び出します。初期投資後にはかなりの節約になります。質問は？

O（2n）= O（n）に関して、それは良好なフォローアップです。 Big-Oの複雑さのルールでは、効率を比較するときには、規模の大きさに関心があると言われています。だから、n = 1000を見ていたとします。 O（n）= 1000、O（2n）= 2000であるが、O（n ）= 1,000,000である。 O（n）はO（2n）とほぼ同じですが、O（n ）と比較すると大きな違いです。同様に、O（n + 1）= 1001で、O（n）とほとんど変わらない場合。ですから、一般的には、先行する言葉、つまり方程式の最も重要な値が重要なものであると言います。私たちは本当に余分な言葉に興味がありません。具体的な係数は実際に結果に影響を与えないので、実際には関心がありません。

まだ質問がありましたら、このサイトでいくつかの追加情報をご覧ください。 https://justin.abrah.ms/computer-science/big-o-notation-explained.html