algorithm - 実行時間は? T(n) = 2T(n-1) + 3T(n-2)+ 1

Question

指数関数的な実行時間を持つフィボナッチ数列に似ていることがわかりました。ただし、この再帰関係にはさらに分岐があります。の漸近限界はT(n) = 2T(n-1) + 3T(n-2)+ 1何ですか?

Answer 1

通常、T(0) と T(1) についていくつかの仮定を行う必要があります。それらの数は指数関数的に多くなり、それらの値によって T(n) の関数形式が決まる可能性があるためです。ただし、この場合は問題ではないようです。

次に、この形式の再帰関係は、それらの特徴的な多項式を見つけることによって解決できます。この記事を見つけました: http://www.wikihow.com/Solve-Recurrence-Relations

根が 3 と 1 の特性多項式が得られたので、 の形が推測できT(n) = c_1*3^n + c_2ます。特に、T(n) = 1/2*3^n - 1/4は再帰関係を満たし、これを検証できます。

1/2*3^n - 1/4 = 2*T(n-1) + 3*T(n-2) + 1
              = 2*(1/2*3^(n-1) - 1/4) + 3*(1/2*3^(n-2) - 1/4) + 1
              = 3^(n-1) - 1/2 + 1/2*3^(n-1) - 3/4 + 1
              = 3/2*3^(n-1) - 1/4
              = 1/2*3^n - 1/4

したがって、それはそれを与えるでしょうT(n) = Theta(3^n)。ただし、これは繰り返し条件を満たす唯一の関数ではない可能性があり、他の可能性も定義した値T(0)とによって異なりますT(1)が、それらはすべて である必要がありますO(3^n)。

Answer 2

このタイプの再帰は、非同次再帰関係と呼ばれ、最初に同次再帰 (最後に定数がないもの) を解決する必要があります。興味がある場合は、その背後にある数学を読んでください。

簡単な方法を紹介します。数式をwolfram-alphaに入力するだけで、次の結果が得られます。

、

これは明らかに指数関数的な複雑さです:O(3^n)