コーディングのインタビューから引用:
increment
O(1) 時間の複雑さで無限のバイナリ カウンターをどのように実装しますか?
一番右の の 1 番目と 2 番目の位置を計算しようと思ったの0
ですが、これを実装する方法がわかりません。
「無限カウンター」とは、無限回 (MAX_INT より大きい) インクリメントできることを意味します。
コーディングのインタビューから引用:
increment
O(1) 時間の複雑さで無限のバイナリ カウンターをどのように実装しますか?
一番右の の 1 番目と 2 番目の位置を計算しようと思ったの0
ですが、これを実装する方法がわかりません。
「無限カウンター」とは、無限回 (MAX_INT より大きい) インクリメントできることを意味します。
バイナリカウンターの場合...
カウンターを「通常の」ビットパターンに保ちたい場合、基本的にはできません-少なくとも、償却された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) であると仮定していますが、これは無限の数のオブジェクトでトリッキーになる可能性があります...
したがって、単純な実装では、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) カウンターの増分のみを求めている場合、カウンターは数値のリンクされたリストとして実装でき、アイテムの合計がカウンターの値になります。
増分は、最後の項目に 1 を追加すること、または前の値が (Max-1) より大きい場合は新しい項目 = 1 を追加することと同じです。
リスト内の最大 2 つのアイテムを常にチェックするため、インクリメントは O(1) になります。
光沢のある新しいカウンターで他の算術をやろうとしないでください:D
私の試み:
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
回転させることは、ブール値のメンバーをトグルするだけです。これは一定です