算法分析

Question

我有一个包含以下伪代码的算法：

R(n)
if(n = 1)
  return 1
else
  return(R(n-1) + 2 * n + 1)

我需要为这个算法执行的乘法次数建立一个递归关系并求解它。

下面的是正确的吗？

R(1) = 0
R(n) = R(n-1) + n^2

Answer 1

您每一步只执行一次乘法。因此，关系将是：

R(n) = R(n-1) + 1

Answer 2

在如图所示的算法中，R(n)是通过将R( n-1 )加到2*n+1来计算的，如果使用乘法来计算2*n，则每级递归将有一个乘法，从而在R(n)的计算中进行n-1次乘法。

为了通过递归来计算，让M(n)是用于计算R(n)的乘法次数。对于i>1，递推边界条件为M(1) =0，递推关系为M(i) = M(i-1) +1。

将“R(1)= 0；R(n) = R(n-1) +n^2”写为乘法次数的递归的错误包括：

·R()已被用作正在计算的函数，因此在乘法次数不正确时重复使用R()

·算法中的每一级递归都会添加一个乘法，而不是n²乘法。

注意，R(n) =1+5+7+ ... + 2n+1 =1+3+5+7+ ... + 2n+1 -3= n²-3；即函数R(n)返回值n²-3。