递增一个无限二进制计数器

本文关键字：一个 无限 二进制 计数器 | 更新日期: 2023-09-27 18:00:23

摘自编码访谈：

在O（1）时间复杂度下，如何用increment实现无限二进制计数器？

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

"无限计数器"意味着您可以无限次递增（大于MAX_INT）。

递增一个无限二进制计数器

对于二进制计数器

如果你想让计数器保持在一个"正常"的位模式，你不能，从根本上说-至少对于总是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）——对于无限多的对象，这可能会变得很棘手。。。

  • 使用某种具有加倍策略的阵列存储。这意味着分摊O（1）
    链接列表也应该起作用
  • 使用琐碎的课本添加。进位对于高位来说是指数级稀少的。进位的平均成本为1+0.5+0.25+…=2，其中O（1）

因此，直接实现已经摊销了O（1）性能。唯一的问题是您需要可变存储。

当观察数字n的单独增量操作时，则平均时间为O（1），但最坏情况为O（log（n））。内存使用率为O（log（n））。

var counter=new List<bool>{false};
void Inc()
{
  while(counter[i])
  {
      counter[i]=false;
      i++;
  }
  if(i==counter.Length)
    counter.Add(true);
  else
    counter[i]=true;
}

如果问题是仅要求增加O（1）计数器，而没有任何其他限制，则计数器可以实现为数字的链表，项目的总和就是计数器的值。

如果之前的值大于（Max-1），则递增相当于在最后一个项上添加1，或者添加新项=1。

由于你总是最多检查列表中的2个项目，因此递增将是O（1）

只是不要尝试用你闪亮的新计数器做其他算术：D

我的尝试：

我们在连续的CCD_ 4或CCD_。

意味着111000111是<1,0><3,1><3,0><3,1>

我可以用以下DS来表示这一点：

节点列表｛数字：布尔，计数器：长｝

1） 如果第一体积为1。它转向0的大部分，并将下一个0变成1。

我们现在检查是否可以聚合1的散货。

2） 如果第一个批量是0，我们将第一个数字设为1。看看我们是否可以聚合1。

示例A:

意味着111000111是<1,0><3,1><3,0><3,1>

读取：三个1位，三个0位，三位1位，一位0位

增量（）

<1,0><3,1><2,0><1,1><3,0>

示例B:

<1,0><3,1><1,0><3,1>

增量（）

<1,0><3,1><1,1><3,0>

聚合：

<1,0><4,1><3,0>

总是会有常量的变化（直到最右边的0位）

而翻转大部分CCD_ 10s只是翻转布尔成员。其为常数

相关文章：