时间戳

首页 > 解决方案 > 计算具有相互依赖关系的递归算法的复杂度

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

问题描述

我最近编写了一个基于递归算法的程序，解决了用 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

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

我是否使用了错误的方法，或者可能以错误的方式使用了这些方法？如果是这样，任何人都可以提供解决方案吗？

编辑：我在 CS Stack Exchange 中问了同样的问题，那里也给出了一个很好的答案。 https://cs.stackexchange.com/questions/124514/calculating-complexity-for-recursive-algorithm-with-codependent-relations

标签： algorithmrecursiontime-complexityrecurrencetiling

解决方案

它是指数的。剩下要做的就是找到基地。首先定义一个向量值函数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)。

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

推荐阅读