增加无限二进制计数器

Question

采访编码采访:

如何实现incrementO(1)时间复杂度的无限二进制计数器？

我想要计算最右边的第一个和第二个位置0,但我不知道如何实现它.

"无限计数器"意味着您可以增加无限次(大于MAX_INT).

Answer 1

对于二进制计数器......

如果你想让计数器处于"正常"位模式,你基本上不能 - 至少不是总是 O(1)而不是摊销的 O(1).

如果它是一个无限计数器,它可以有任意多位.这意味着你可以有多个N位,所有这些都是1.增加该计数器意味着将所有这些位设置为0,这可以合理地假设为O(N)操作.

我们可以在"正常"计算中考虑增量为O(1)的唯一原因是通常处理固定大小的类型,我们可以说(例如)"最多32位需要更改 - 这是一个常量,所以它可以说是O(1)操作."

对于一个柜台......

另一方面,如果你只想在O(1)时间内增加,你就拥有无限的内存,并且你不关心恢复数值需要多长时间,你可以做到这一点,只需要有效地使用一个链表,其长度为计数器大小.

例如,在C#中:

public DodgySolution
{
    public static DodgySolution Zero = new DodgySolution(null);

    private DodgySolution tail;

    private DodgySolution(DodgySolution tail)
    {
        this.tail = tail;
    }

    // This bit is O(1)
    public DodgySolution Increment()
    {
        return new DodgySolution(this);
    }

    // This bit isn't...
    public BigInteger ToBigInteger()
    {
        return tail == null ? BigInteger.Zero
                            : BigInteger.One + tail.ToBigInteger();
    }
}

即使这假设参考分配是O(1) - 但是对于无限数量的对象可能变得棘手......