Временная сложность алгоритма, включая цикл while

Question

У меня есть этот алгоритм, и я хочу проанализировать временную сложность, но я не уверен, что я прав:

n = int(input("Enter Target Value: "))
x = 1
count = 0
while n != x:
    if n % 2 == 0:
        n /= 2
        count +=1
    else:
        n -= 1
        count +=1
print(count)

пока l oop, n / 2 будет иметь временную сложность O (logn) и n-1 будут O (n), поэтому O (logn) + O (n) все равно будет O (logn) в течение l oop. Инициализация 3 будет O (1), поэтому сложность времени выполнения этого al go будет O (logn). Я прав? Спасибо

Answer 1

Результат верный, но рассуждения нет. Оператор n-=1 не будет выполнен O (n) раз, а O (logn) + O (n) фактически O (n) , не O (logn) .

Представьте n в его двоичном представлении. Тогда операция n-=1 будет выполнена столько раз, сколько в этом представлении содержится 1 бит. Оператор n/=2 будет выполняться столько раз, сколько битов в представлении, независимо от того, являются ли они 0 или 1. Это происходит потому, что 1-бит сначала будет преобразован в 0-бит с помощью n-=1 операции, а затем следующая итерация выберет тот же бит (который стал 0) для операции n/=2, которая фактически сбрасывает этот бит.

Так что в худшем случае все значащие биты n являются 1-битными. И тогда у вас есть O (logn) выполнения операции n-=1 и O (logn) выполнения n/=2. В общей сложности l oop составляет 2O (logn) итераций, что дает этому алгоритму O (logn) сложность времени.