algorithm - O(N) 与 O(NlogN)

Question

我在处理 Big-O 表示法时遇到了这个例子

x=n
while(x>0)
{
    y=x
    while(y>0)
    {   
        y=y-1
    }
    x = x/2
}

你能解释一下为什么它看起来有 O(N) 复杂度吗？

这对我来说是新的，但我希望它是 N LogN。

我错过了什么？

谢谢，

编辑:这段代码来自这里 https://www.quora.com/How-can-we-check-for-the-complexity-log-n-and-n-log-n-for-an-algorithm?encoded_access_token=1b7e0a4d10f84d50b5fea810f5a89cea

Answer 1

好吧，让我们看看内部循环体的执行频率:

x =   n:      n
x = n /  2: n /  2
x = n /  4: n /  4
x = n /  8: n /  8
x = n / 16: n / 16
x = n / 32: n / 32
x = n / 64: n / 64
until x < 1

或者放在一起:

n + n / 2 + n / 4 + n / 8 + n / 16 + n / 32 + n / 64 ...

很容易看出与:

n + n - n / 64

现在我们想要一个上限，所以我们可以忽略最后一项。而对于 big-oh，常数也是微不足道的。所以:

O(n)