c++ - 编写并解决计算此代码中乘法次数的递归？

Question

令 M(n) 为函数 fct 的乘法次数。

     //precondition: n>0
     int fct (const int A[], int n) {
          if (n==1)
             return A[0]*A[0];
          else return A[n-1] * fct(A,n-1) * A[n-1];
     }

写出 M(n) 的递归关系，其中 n 是数组中的元素数

求解递归关系以获得关于 n 的 M(n)

用大 O 表示法写出第 2 部分的结果表达式

所以这是一个测验，我有答案，但不太确定这是如何计算的，M(n)=2n-1 与 O(n)..我不知道这是如何确定的，有人可以解释一下吗？谢谢

Answer 1

让我们看看每个调用的作用。每次调用，当 n > 1 时，

• 正好做两次乘法，然后
• 对大小为 n - 1 的问题进行递归调用

因此，我们可以将递归写成

• M(1) = 1
• M(n) = 2 + M(n-1)

如果您使用迭代方法，您会注意到这种模式：

• M(1) = 1
• M(2) = M(1) + 2 = 3
• M(3) = M(2) + 2 = 5
• M(4) = M(3) + 2 = 7
• ...
• M(n) = 2n - 1

现在你有了这个，你可以将它渐近地写为 M(n) = Θ(n)。

希望这可以帮助！