私は最近テストを行いました...質問は長い話であり、解決策はF（n）= 2 * F（n-1）+ 2 * F（n-2）に要約されました...
動的計画法を使用したO（n）ソリューションがありました...しかし、審査官は満足していませんでした...
私の解決策は、計算時にすべてのF（n）を配列に格納することでした。O（n）時間がかかりました。前の2つの要素だけが必要なので、2つの変数だけを使用することで、スペースの問題を解決できます。
ただし、O（n）は十分に高速ではありません...
この関数はフィボナッチ関数のように見え、フィボナッチ数はO（lg n）時間で生成できます...しかし、私の問題に対してO（lg n）ソルンを取得できません。
だから私の質問は、関数の時間計算量をどのように改善するのですか？
まったく同じ方法です。繰り返しをマトリックス形式で表現します; これにより、問題が行列のn乗を見つけることになります。これは、log（n）時間で実行できます。
線形漸化式（これは）には閉じた式があります。
これには、特性多項式を解くことが含まれます。この場合は、次のようになります。
t^2 - 2*t - 2 = 0 (since F(n) - 2 * F(n-1) - 2 * F(n-2) = 0)
t1とt2がこの2次方程式の（複素）解である場合、式は次のようになります。
F(n) = a * t1^n + b * t2^n
ここで、aとbは定数であり、初期条件（つまり、この場合はF（0）とF（1）の値）から見つけることができます。つまり
F(0) = a + b
F(1) = a * t1 + b * t2
aとbを解く：
a = ( t2 * F(0) - F(1) ) / ( t2 - t1 )
b = ( t1 * F(0) - F(1) ) / ( t1 - t2 )
この特定の場合、特性多項式の根は次のとおりです。
t1 = 1 + sqrt(3)
t2 = 1 - sqrt(3)
あなたのソリューションでは、O(n) メモリも使用しました。
単純なループを使用して、n 番目のフィボナッチ要素を計算できます。
保存する必要があるのは、最後の 3 つの要素 (a1、a2、a3) だけです。各反復で、a1 を a2 に更新し、a2 を a3 に更新し、a3 を old(a1) + old(a2) に更新します。 (この目的のために 2 つの一時変数を使用できます)。
したがって、ランタイム O(n) O(1) メモリのみの単純なアルゴリズムが得られます。