1

我想写它的分析是 o(n) 的幂递归函数：这是我的想法是真的吗？或者，如果对这段代码的分析不是 o(n)，任何人都可以帮我更改它以使其更好吗？提前致谢

  power(int x , int n)
  {
      if(n==0)
        return 1;
      else
        return x*power(x,n-1);
  }
4

5 回答 5

1

有两个问题：

  1. N 到 0 的幂是 1。这必须是常数 O(1)。
  2. N 到 1 的幂是 N。这也必须是常数 O(1)。

之后，代码应该可以工作。它将在功率的线性时间内表现，因此它将是 O(k)。

于 2013-11-07T20:25:30.460 回答
1

这个方法是 O(k)，而不是 O(n)，因为它会执行k递归调用。此外，基本情况k应该0返回1，而不是n。

于 2013-11-07T20:25:48.783 回答
1

这是 O(n) 时间，因为您正在从输入 n 倒计时到 n 为 0 的位置。

于 2013-11-07T20:25:57.337 回答
1

您正在递归地调用您的函数“k+1”次。power(10,3) 的示例，您进行以下函数调用

power(10,3)  -
power(10,2)   |  k+1 times
power(10,1)   |
power(10,0)  -

因此复杂度是 O(k) 而不是 O(n) ！

于 2013-11-07T20:26:11.033 回答
1

您正在调用“k”次您的函数，它的上限与它的下限匹配。所以我认为这是 Theta(k)

于 2013-11-07T20:29:00.200 回答