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

Если вы обнаружите, сколько раз работает внутренний цикл, вы обнаружите сложность кода.Внутренний цикл выполняется n + n / 2 + n / 4 + ... n / k (где n / k> 0) раз.Максимальное значение n / 2 + n / 4 + ... + n / k part равно n-1.Таким образом, код не может выполняться более 2n-1 раз, делая верхнюю границу 2n-1, которая равна O (n)

Answer 2

Хорошо, давайте посмотрим, как часто выполняется тело внутреннего цикла:

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

Теперь нам нужна верхняя граница, поэтому мы можем игнорировать последний член.И для биг-о, константа тоже незначительна.Итак:

O(n)