0

コーディングのインタビューから引用:

incrementO(1) 時間の複雑さで無限のバイナリ カウンターをどのように実装しますか?

一番右の の 1 番目と 2 番目の位置を計算しようと思ったの0ですが、これを実装する方法がわかりません。

「無限カウンター」とは、無限回 (MAX_INT より大きい) インクリメントできることを意味します。

4

4 に答える 4

7

バイナリカウンターの場合...

カウンターを「通常の」ビットパターンに保ちたい場合、基本的にはできません-少なくとも、償却されたO(1)ではなく、常にO(1)ではありません。

無限カウンターの場合、任意の数のビットを持つことができます。つまり、すべてが 1 の N ビットをいくつも持つことができます。そのカウンターをインクリメントするということは、これらのビットをすべて 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 which 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;
}
于 2013-02-21T21:08:05.570 に答える
2

質問が他の制限なしに O(1) カウンターの増分のみを求めている場合、カウンターは数値のリンクされたリストとして実装でき、アイテムの合計がカウンターの値になります。

増分は、最後の項目に 1 を追加すること、または前の値が (Max-1) より大きい場合は新しい項目 = 1 を追加することと同じです。

リスト内の最大 2 つのアイテムを常にチェックするため、インクリメントは O(1) になります。

光沢のある新しいカウンターで他の算術をやろうとしないでください:D

于 2013-02-21T21:13:24.277 に答える
-1

私の試み：

1連続またはで集計を保持し0ます。

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>であることを意味します

読み：31桁、30桁、31桁、10桁

インクリメント（）

<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桁まで）

sの大部分を1回転させることは、ブール値のメンバーをトグルするだけです。これは一定です

于 2013-02-21T21:41:39.980 に答える