algorithm - 在 Big-O 表示法中找到效率

Question

我对以下问题有疑问

考虑以下嵌套循环结构。使用“big-o”符号根据变量 n 对其效率进行分类。假设由省略号 (...) 表示的语句需要四个主内存访问（每个需要 1 微秒）和两个磁盘文件访问（每个需要 1 毫秒）。如果 n 为 1000，则以毫秒为单位表示此构造执行所需的时间。

x = 1;
do
{
    y = n;
    while (y > 0)
    {
    ...
        y--;
    }
    x *= 2;
} while (x < n*n);

score 1 · Accepted Answer

带有 y 的内循环是 O(n)。

外循环运行 x = 1, 2, 2^2, 2^3, ... 2^k < n * n。因此它在 O(log(n*n)) 中运行，即 O(2 * log(n))

因此复杂度为 O(n * log(n))

score 0 · Accepted Answer

只是为了对另一个答案添加更多解释，代码的一个显着部分是 x *= 2; 即翻倍。所以这部分不是线性的。所以你应该考虑log2。

因此，x 将在 log2(n*n) 中达到 n*n。= log2(n^2) = 2 x log2(n)。

y 倒计时是线性的 - 所以是 O(n)

循环中有一个循环，因此您可以将两个操作相乘，如下所示：

n * 2 x log2(n) = O(n * 2 * log2(n))。然后你取出常数因子得到：O(n * log2(n))

2 回答 2