Сложность времени приращения двоичного счетчика?

Question

я следующий псевдокод приращения двоичного счетчика:

Increment(B) 
    i=0 
    while B[i]=1 
     flip B[i] to zero 
     increment i by 1 
    b[i]=1 

Я сказал, что во время выполнения является O (журнал N), но я не могу понять, почему - петля выглядит, как он может посетить все бит.

Что мне не хватает?

Answer 1

Если у вас есть двоичный счетчик, представляющий число n, тогда будет Θ (log n) разных бит (так как каждый бит представляет экспоненциально большие и большие значения). Если вы посмотрите на количество b, количество бит, тогда должно быть легко увидеть, что время выполнения вышеописанного алгоритма равно O (b), так как каждый бит посещается не более одного раза. Однако, поскольку b = Θ (log n), временная сложность заканчивается O (log n).

Надеюсь, это поможет!