算法分析 : Big-O explanation

Question

我目前正在上算法课。以下是我在测验中做错的一个问题:基本上，我们必须用大 O 表示法表示最坏情况下的运行时间:

int foo(int n) 
 {
    m = 0;
   while (n >=2)
   {
    n = n/4;
    m = m + 1;
   }   
   return m;
 }

我不明白最坏情况的时间为什么不是 O(n)。希望得到解释。谢谢。

Answer 1

foo 通过将 n 除以 4 并使用 m 计算 n 中 4 的个数来计算 log4(n) > 作为柜台。最后，m 将是 n 中 4 的个数。所以它与 m 的最终值成线性关系，它等于 n 的以 4 为底的对数。那么算法就是O(logn)，也就是O(n)。