用广义关系计算递归算法的复杂性

Question

我最近编写了一个基于递归算法的程序，解决了用2x1多米诺骨牌铺设3xn板的方式的数量：

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）。 $$ 这些是完全相同的复发，但有不同的初始值。

一个简单的诱导显示 $ f（n）= 0 $ 对于奇数 $ n $ 时 $ g（n）= 0 $ even $ 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} ）（2 - \ sqrt {3}）^ {（n-1）/ 2}。 $$ 这个序列是 a001353 。

---

或者，我们可以注意到 $$ \ begin {pmatrix} f（n）\\ g（n + 1） \结束{pmatrix}= \ begin {pmatrix} 1＆2 \\ 1和3 \结束{pmatrix} \ begin {pmatrix} f（n-2）\\ g（n-1） \结束{pmatrix} $$ 它遵循 $$ \ begin {pmatrix} F（2M）\\ g（2m + 1） \结束{pmatrix}= \ begin {pmatrix} 1＆2 \\ 1和3 \结束{pmatrix} ^ m \ begin {pmatrix} 1 \\ 1 \结束{pmatrix} $$ 矩阵的特征值是 $ 2 \ pm \ sqrt {3} $ ，因此我们被引导到如上所述的公式。