java - 确定特定循环的 Big(O) 效率

Question

我被要求确定这个循环的大 O 符号。

    int x = 1;
    int n = 1000;
    while (x < (n*n))
    {
        int y = n;
        while (y > 0)
        {
            y = y-1;
        }
        x = x+x;
    }

现在我看到这是一个嵌套循环。但这绝对不是 N^2，对吗？我明白是什么让某些事情成为 O(n) 或 O(log(n))，但我将如何确定一个特定的循环，比如这个循环？

Answer 1

内部循环从 n 到 0，所以它是 O(n)。

外循环

while (x < (n*n)) {
    ...
    x = 2*x;
}

是对数，从 1 到 n*n，即 O(log(n² )) = O(2 log n) = O(log n)。

由于循环是嵌套的，因此您将复杂性相乘得到 O(n log n)。