math - バイナリカウンターをインクリメントする時間の複雑さ?

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) であることが簡単にわかります。これは、各ビットが最大 1 回アクセスされるためです。ただし、b = Θ(log n) であるため、時間計算量は O(log n) になります。

お役に立てれば！