algorithm - 算法分析

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-1) 与 2*n+1 相加来计算 R(n)。如果使用乘法计算 2*n，则每级递归将有一次乘法，因此在计算 R(n) 时会进行 n-1 次乘法。

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