c++ - 对确定 Big-O 表示法感到困惑？

Question

所以，我真的不懂大 O 符号。我的任务是确定此代码段的“O 值”。

for (int count =1; count < n; count++) // Runs n times, so linear, or O(N)
    { 
        int count2 = 1;        // Declares an integer, so constant, O(1)

        while (count2 < count) // Here's where I get confused. I recognize that it is a nested loop, but does that make it O(N^2)?
            {
                count2 = count2 * 2;   // I would expect this to be constant as well, O(N)
            }
    }

Answer 1

O(f(n))=g(n)

这意味着对于某些值 k，f(n)>g(n) 其中 n>k。这给出了函数 g(n) 的上限。

当要求您为某些代码查找 Big O 时，

1) 尝试根据 n 计算执行的计算次数，从而得到 g(n)。

2) 现在尝试估计g(n) 的上限函数。这就是您的答案。

让我们将此过程应用于您的代码。

让我们数一数计算的次数。 声明 和乘以 2 语句需要 O(1) 时间。但是这些是重复执行的。我们需要找出它们被执行了多少次。

外层循环执行n 次。因此第一个语句执行了 n 次。现在内循环执行的次数取决于 n 的值。对于给定的 n 值，它执行 logn 次。

现在让我们计算执行的计算总数，

log(1) + log(2) + log(3) +.... log(n) + n

请注意，最后一个 n 用于第一条语句。简化上述系列我们得到:

= log(1*2*3*...n) + n

= log(n!) + n

我们有

g(n)=log(n!) + n

让我们猜猜 log(n!) 的上限。

因为，

1.2.3.4...n < n.n.n...(n times)

因此，

log(n!) < log(n^n) for n>1

暗示

log(n!) = O(nlogn).

如果你想要一个正式的证明，检查this出去。由于 nlogn 比 n 增长得更快，因此我们有:

O(nlogn + n) = O(nlogn)

因此你的最终答案是O(nlogn)。