算法的递归方程

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.