COD依存関係を用いた再帰的アルゴリズムの複雑さの計算

Question

私は最近、再帰的アルゴリズムに基づいていたプログラムを書いて、2x1ドミノで3 x 2ボードをタイルする方法の数を解く：

f（n）= f（n - 2）+ 2 * g（n - 1）

g（n）= g（n - 2）+ f（n - 1）

f（0）= 1、f（1）= 0、g（0）= 0、g（1）= 1

再帰ツリーや拡張など、私が知っている方法を使用して複雑さを計算しようとしましたが、何も答えませんでした。実際に私はそのような再帰に出かけたことがありませんでした。ここで、関係は硬化依存性です。

私は間違った方法を使っていますか、それとも間違った方法でメソッドを使用することはできますか？もしそうなら、誰かが解決策を提供することができますか？

Answer 1

$ f（n）= g（n + 1） - g（n-1）$ に注意してください。したがって $$ G（N + 1）~G（N - 1）= G（N - 1） - G（N - 3）+ 2G（N - 1）、 $$ それを意味する $$ g（n + 1）= 4g（n - 1） - g（n - 3）。 $$

同様に、 $ g（n）=（f（n + 1） - f（n-1））/ 2 $ など $$ （F（N + 1）-F（N-1））/ 2=（F（N-1）-F（N-3））/ 2 + F（N-1）、 $$ それを意味する $$ F（n + 1）= 4f（n - 1） - f（n - 3）。 $$ これらは、異なる初期値ではまったく同じ再循環です。

奇妙な $ n $ のための $ f（n）= 0 $ である単純な誘導 $ g（n）= 0 $ 氏は、 $ n $ （これもそれらの意味的意味からも続きます） 。

再発を使用して、 $ n $ でさえ簡単に入手できます。 $$ f（n）=（1/2 + 1/2 \ sqrt {3}）（2 + \ sqrt {3}）^ {n / 2} +（1/2 - 1/2 \ sqrt {3}）（ 2 - \ sqrt {3}）^ {n / 2}。 $$ このシーケンスは a001835

です。

同様に、奇数 $ n $ の場合、 $$ g（n）=（1/2 + 1 / \ sqrt {3}）（2 + \ sqrt {3}）^ {（n-1）/ 2} +（1/2 - 1 / \ sqrt {3} ）^ {（n-1）/ 2}）（2 - \ sqrt {3}）^ {（n-1）/ 2}。 $$ このシーケンスは、 A001353

です。

---

または私達はそれに気づくことができます $$ \ begin {pmatrix} f（n）\\ g（n + 1） \ end {PMatrix}= \ begin {pmatrix} 1＆2 \\ 1＆3 \ end {PMatrix} \ begin {pmatrix} f（n-2）\\ G（N-1） \ end {PMatrix} $$ それはそれに続く $$ \ begin {pmatrix} f（2m）\\ G（2m + 1） \ end {PMatrix}= \ begin {pmatrix} 1＆2 \\ 1＆3 \ end {PMatrix} ^ M. \ begin {pmatrix} 1 \\ 1 \ end {PMatrix} $$ 行列の固有値は $ 2 \ pm \ sqrt {3} $ ですので、上記のように式につながります。