嵌套if算法分析

Question

我正在为算法找出大的O符号，我想知道我是否正确地记下了这一点。

我目前正在分析以下代码：

int expon(int x, int n) /* n > 0 */
{   
  if (n==0) return 1;
  else
  {
    if even(n) return expon(x*x, n/2);
    else
      return expon(x, n-1)*x;
  }
}

到目前为止，这就是我所得到的:第一个if语句，它检查是否n=0只是一个常量，它得到的全部是c。

调用偶数( n )检查的第二个if语句执行n次，因此接收n次，返回expon(x*x，n/2)执行n次，因此if语句为n^2。最后一次语句只执行一次其他所有操作，因此我们可以调用它。

最后，我们将所有这些加起来，得到: c+c(n^2)。如果我们想用bigO表示法写这个，我们会删除常量，只写O(n^2)。

如果我错了，有人能纠正我吗？我觉得我没有正确地分析这个(特别是第二个if)，也没有正确地添加/乘以n和c的总和。

谢谢一堆人！

Answer 1

让我们以一种不同的方式来看待这个问题:算法的运行时由n决定，x的值只影响最后得到的值。让我们看看n发生了什么：n的值要么下降1，要么在递归调用中减半。

如果n是偶数，那么我们除以2并执行递归调用。

如果n是奇数，那么我们减去一个，然后它又变成了偶数。因此，对于奇数，我们执行一个额外的调用，使该数字为偶数。

因此，我们可以观察到，n下降了一个或一半(交替)。这个模式是O(log )。如果我们加倍n，那么我们只需要再调用一到两个递归调用就可以完成算法，这就是O(log )所表示的。如果是O(n^2)，那么增加一个n会使算法运行时增加很多。

Answer 2

您使用的方法看起来大部分都是正确的。然而，数量级为O(log )。O(n^2)随着n的增加而增加，这随着n的增加而增加。例如，当n为2、4和8时，循环运行1、2和3次。

您的实现的问题在于它需要：

else if (n == 1) return x;