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)，因为每个位最多被访问一次。然而，由于 b = Θ(log n)，时间复杂度最终为 O(log n)。

希望这可以帮助！