定义算法的时间复杂度（log n 或 n）

Question

 int silly(int n, int m) {
 if (n < 1) return m;
 else if (n < 10)
  return silly(n/2, m);
 else
  return silly(n - 2, m);
}

这个算法是 O(log n) 还是 O(n) 的 Big-Oh 符号？

Answer 1

如果优化器真的很好，那就是 O(1)。该代码等效于简单的return m.

假设它是给定的，我们可以忽略if( n < 10 )条件，因为当 n 很小时，这是几次迭代。当 n 很大时，我们正在寻找最坏的情况。

剩下的就是递归到silly(n - 2, m)其中每隔一个整数倒计时。那是 n/2 次操作。我们删除常数使其成为 O(n)。