算法分析嵌套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。

调用 even(n) 检查的第二个 if 语句执行了 n 次，因此接收到 n 并且 return expon(x*x, n/2) 执行了这 n 次也接收到 n。这样 if 语句就是 n^2。它处理其他所有事情的最后一条语句只执行一次，所以我们可以称它为 c。

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

如果我在这里错了，谁能纠正我？我觉得我没有正确分析这个(尤其是第二个如果)，也没有正确地添加/乘以 n 和 c 的总数。

非常感谢!

Answer 1

让我们换个角度看:算法的运行时间由n决定，x的值只影响最后得到的值.那么让我们看看 n 会发生什么:n 的值要么减 1，要么在递归调用中减半。

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

如果 n 是奇数，那么我们减一，然后它再次变为偶数。因此，对于奇数，我们执行一次额外调用以使数字变为偶数。

因此我们可以观察到 n 下降一或减半(交替)。该模式是 O(log n)。如果我们将 n 加倍，那么我们只需要再进行一两次递归调用即可完成算法，这就是 O(log n) 所表达的。如果它是 O(n^2)，那么将 n 增加 1 会大大增加算法的运行时间。