算法分析：Big-O解释

Question

我目前正在学习 class 算法。以下是我从测验中做错的问题：基本上，我们必须用大 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)。

Answer 2

让我们假设最坏的情况是 O(n)。这意味着该函数至少需要 n 个步骤。

现在让我们看看循环，n 在每一步都除以 4（或 2²）。因此，在第一次迭代中，n 减少到 n/4，在第二次中，减少到 n/8。它不是线性减少的。它被减少了 2 的幂，所以在最坏的情况下，它的运行时间是 O(log n)。

Answer 3

计算可以用递归公式表示：

f(r) = 4*f(r+1)

解决方案是

f(r) = k * 4 ^(1-r)

其中 ^ 表示指数。在我们的例子中，我们可以说 f(0) = n

所以 f(r) = n * 4^(-r)

在结束条件下求解 r 我们有：2 = n * 4^(-r)

在两边使用log，log(2) = log(n) - r* log(4)可以看到

r =  P * log(n);

没有更多的分支或内部循环，假设除法和加法是 O(1) 我们可以自信地说该算法运行 P * log(n) 步骤因此是 O((log(n)).

吹毛求疵的角落：C int 通常意味着最大值是 2^32 - 1 所以在实践中它只意味着最大 15 次迭代，这当然是 O(1)。不过我觉得你老师的意思真的是O(log(n)).

Algorithm Analysis: Big-O explanation