0

摘自编码面试：

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

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

“无限计数器”意味着您可以增加无限次（大于 MAX_INT）。

4

4 回答 4

7

对于二进制计数器...

如果您想将计数器保持在“正常”位模式，从根本上讲，您不能 - 至少不是总是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) - 这可能会因为无限数量的对象而变得棘手......

于 2013-02-21T21:02:57.960 回答
3
  • 使用某种具有加倍策略的阵列存储。这意味着分配是摊销的 O(1)
    链表也应该可以工作。
  • 使用微不足道的教科书添加。对于更高的位，进位呈指数级罕见。携带的平均成本是 1+0.5+0.25+... = 2 其中 O(1)

所以一个直接的实现已经摊销了 O(1) 的性能。唯一的问题是您需要可变存储。

在查看 number 的单个增量操作时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;
}
于 2013-02-21T21:08:05.570 回答
2

如果问题只是要求增加 O(1) 计数器而没有任何其他限制，则您的计数器可以实现为数字的链接列表，并且项目的总和是您的计数器的值。

如果之前的值大于 (Max-1)，则递增将等同于在最后一项中添加 1 或添加新项 = 1。

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

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

于 2013-02-21T21:13:24.277 回答
-1

我的尝试：

我们在连续的1or上保持聚合0。

意思是 111000111 是 <1,0> <3,1> <3,0> <3,1>

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

节点列表 { digit : bool, counter: long}

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>

总会有 const 的更改次数（直到最右边的 0 位）

并且转动大部分1s 只是切换布尔成员。这是恒定的

于 2013-02-21T21:41:39.980 回答