算法递归方程

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)，如果n>1

这是正确的吗?我还必须为这个算法执行的乘法次数设置一个递归式。请帮助。

Answer 1

您在这里建立的递归关系是正确的。它基本上就是你把一个问题写成一个子问题的形式。

现在是乘法的次数。记住两件事。

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

现在是你的递归式

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

T(n) = 5*T(n-1) - 6.T(n-2)，如果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