algorithm - n> 3の場合、関係T（n）= T（n-1）+ T（n-2）+ T（n-3）の時間計算量を見つける

Question

フィボナッチ数列にやや似ています

アルゴリズムの実行時間は次の式で与えられます。

T (n) =T (n-1)+T(n-2)+T(n-3) if n > 3

= nそれ以外の場合、このアルゴリズムの順序は？

誘導法で計算した場合

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

T（n）をある関数aⁿ<br>と仮定すると、aⁿ= a ^n-1 + a ^n-2 + an ^-3
=>a³=a²+a+ 1

私の計算によると、複雑な解を与える上記の方程式の根も

a = 1.839286755
a = 0.419643 - i ( 0.606291) 
a = 0.419643 + i ( 0.606291) 

さて、どうすればさらに先に進むことができますか、またはこれのための他の方法はありますか？

Answer 1

私の記憶が正しければ、特性方程式の根を決定すると、T(n) はそれらの根の累乗の線形結合になる可能性があります。

T(n)=A1*root1^n+A2*root2^n+A3*root3^n

したがって、ここでの最大の複雑さは (maxroot)^n になると思います。ここで、maxroot はルートの最大絶対値です。したがって、あなたの場合は〜1.83 ^ nです

Answer 2

プログラムの実行時間に対して漸近分析が行われ、入力によって実行時間がどのように増加するかがわかります。

（あなたが言及したような）漸化式の場合、2段階のプロセスを使用します。

1. 再帰ツリー法を使用して実行時間を見積もります。
2. 置換方法を使用して見積もりを検証（確認）します。

これらのメソッドの説明は、任意のアルゴリズムテキスト（Cormenなど）にあります。

Answer 3

O(3^n) である 3+9+27+......3^n のように近似できます。