algorithm - 算法的递归方程

Question

我对递归方程概念很陌生，需要以下算法的帮助

G(n)
Require: A positive integer n.
if n <= 1 then
return n
else
return 5*g(n - 1) - 6* g(n- 2)
end if

我想出了以下递归方程:

T(n) = n, if n<=1,
T(n) = 5*T(n-1) - 6.T(n-2), if n>1

这是否正确，我还必须为该算法执行的乘法次数设置一个循环。请帮忙。

Answer 1

你在这里建立的递归关系是正确的。基本上，您以较小的子问题的形式编写问题。

现在是乘法的次数。请牢记两点。

1. 您需要在递归关系中下降以达到基本情况的步骤数(在本例中为 n<=1)。
2. 每种情况下的操作次数。

现在为您的重现。

T(n) = n, if n<=1

T(n) = 5*T(n-1) - 6.T(n-2), if n>1

你有一个递归，在每一步将一个问题变成两个子问题，并且在每一步 n 的值减少 1

T (n) = 5*T(n-1) - 6*T(n-2)T(n-1) = 5*T(n-2) - 6*T(n-3)

所以 n 步每次分支成 2 个子问题，所以你将有2 * 2 * ... 2(O(n) 时间)因此，您的问题大约有 2^n 个步骤，因此 O(2^n)每一步有2次乘法和1次减法。

乘法次数的递归是这样的

T(n) = T(n-1) + T(n-2) + 2

所以乘法的次数大约为 ( 2^n )*2。