计算具有相互依赖关系的递归算法的复杂度

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

我尝试使用我知道的方法（例如递归树和扩展）来计算复杂度，但 none 得出了任何答案。其实我从来没有遇到过这种关系相互依赖的递归。

是我用错了方法，还是用错了方法？如果是这样，谁能提供解决方案？

Answer 1

它是指数级的。剩下要做的就是找到基地。首先定义一个向量值函数V(n)如下。

       ( F(n)   )
V(n) = ( F(n-1) )
       ( G(n)   )
       ( G(n-1) )

现在我们有 V(n) = A * V(n-1)，其中 A 是一些矩阵。如果我没有搞砸的话，那个矩阵是：

[ 0 1 2 0 ]
[ 1 0 0 0 ]
[ 1 0 0 1 ]
[ 0 0 1 0 ]

根据您的初始条件：

       ( 1 )
V(1) = ( 0 )
       ( 1 )
       ( 0 )

现在我们有了以下规则。 V(n+1) = A^n * V(1)。如果您熟悉矩阵数学，就会知道这个指数的增长由主特征值决定。哪个（检查 https://www.dcode.fr/matrix-eigenvalues 后）恰好是 sqrt(2+sqrt(3)).

所以F(n) = O(sqrt(2+sqrt(3))^n).

（这背后的理论通常用斐波那契数列来解释，但它可以应用于任何差分方程。）

Calculating complexity for recursive algorithm with codependent relations