遞增二進制計數器的時間複雜度？

Question

我爲遞增二進制計數器以下僞代碼：

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

我已被告知，運行時間爲O（log n）的，但我不明白爲什麼 - 循環看起來像它可能會訪問所有位。

我錯過了什麼？

Answer 1

如果您有一個二進制計數器代表數字n，那麼總共將有Θ（log n）個不同的位（因爲每個位代表指數級別越大越大的值）。如果查看數量b和位數，那麼應該很容易看出上述算法的運行時間是O（b），因爲每個位最多訪問一次。但是，由於b = Θ（log n），時間複雜度最終爲O（log n）。

希望這會有所幫助！