8

可能かどうかはわかりませんが、少し理にかなっているように思えます。これらの操作を実行できるデータ構造を探しています。

  • O(log n) でアイテムを挿入する
  • O(log n) でアイテムを削除する
  • 任意の k に対して、O(1) の k 番目に小さい要素を検索/編集します (O(1) インデックス)

もちろん、編集によって要素の順序が変更されることはありません。どういうわけかそれを可能にするのは、昇順で要素を 1 つずつ挿入することです。したがって、たとえば 5 回目の挿入を試みた場合、この前の 4 つの要素はすべてそれよりも小さく、これより後のすべての要素は大きくなります。

4

6 に答える 6

6

要求された時間の複雑さがそのようなデータ コンテナーで可能かどうかはわかりません。しかし、これらの複雑さをほとんど達成するいくつかのアプローチがあります。

最初の 1 つは、O(1) の挿入とインデックス作成を伴う階層化されたベクトルですが、O(sqrt N) の削除です。このコンテナーには約 10000 要素しかないと予想され、sqrt(10000)/log(10000) = 7 であるため、ここで必要なパフォーマンスがほぼ得られます。階層化されたベクトルはリング バッファーの配列として実装されるため、要素を削除するには、すべての要素を移動し、リング バッファーでそれを追跡し、次の各リング バッファーから 1 つの要素をその前のリング バッファーに移動する必要があります。このコンテナーでのインデックス作成は、リング バッファーの配列でのインデックス作成と、リング バッファー内でのインデックス作成を意味します。

まったく同じ複雑さを持つ、階層化されたベクターに非常に似た別のコンテナーを作成することができますが、キャッシュに適しているため、少し高速に動作します。値を格納するために N 要素の配列を割り当てます。また、sqrt(N) 要素の配列を割り当てて、インデックスの修正 (ゼロで初期化) を格納します。100 要素コンテナーの例で、それがどのように機能するかを示します。インデックス 56 の要素を削除するには、要素 57..60 を位置 56..59 に移動し、インデックス修正の配列で要素 6..9 に 1 を追加します。84 番目の要素を見つけるには、インデックス修正の配列 (値は 1) で 8 番目の要素を検索し、その値をインデックス (84+1=85) に追加してから、メイン配列から 85 番目の要素を取得します。メイン配列の要素の約半分が削除された後、コンテナ全体を圧縮して連続したストレージを実現する必要があります。これは、O(1) 累積複雑度のみを取得します。リアルタイム アプリケーションの場合、この操作はいくつかの小さな手順で実行できます。

このアプローチは、インデックス作成に O(M) 時間、削除に O(M*N 1/M ) 時間、挿入に O(1) 時間を要して、深さ M のトライに拡張することができます。値 N (M-1)/M、 N (M-2)/M、...、 N 1/Mを格納する N 要素の配列を割り当てるだけです。-インデックス修正を格納するための要素配列。要素 2345 を削除するには、メイン配列で 4 要素を移動し、最大の「修正」配列で 5 要素を増やし、次の要素で 6 要素を増やし、最後の要素で 7 要素を増やします。このコンテナーから要素 5678 を取得するには、要素 5、56、567 のすべての修正を 5678 に追加し、その結果を使用してメイン配列にインデックスを付けます。「M」に異なる値を選択すると、インデックス作成操作と削除操作の複雑さのバランスを取ることができます。たとえば、N=65000 の場合、M=4 を選択できます。そのため、インデックス作成に必要なメモリ アクセスは 4 回だけで、削除は 4*16=64 のメモリ ロケーションを更新します。

于 2012-05-09T15:28:42.797 に答える
1

最初に、 kが実際に乱数である場合、問題が完全に異なる可能性があることを考慮する価値があるかもしれないことを指摘したいと思います。k番目に小さい要素を求め、kは使用可能な要素の範囲で均一にランダムになります。基本的に...要素をランダムに選択します。そして、それは非常に異なる方法で行うことができます。

ここでは、任意の場合でも、特定のkを実際に選択する必要があると想定しています。

要素が順番に挿入されるという強い前提条件を考えると、簡単な解決策があります。

  • 要素は順番に指定されているので、配列に1つずつ追加するだけです。つまり、いくつかの（無限の）テーブルTと、カーソルc（最初はc：= 1）があり、要素を追加するときに、T [c]：= xおよびc：= c+1を実行します。
  • k番目に小さい要素にアクセスする場合は、T[k]を見てください。

もちろん、問題は、要素を削除すると、テーブルにギャップが作成され、要素T [k]がk番目に最小ではなく、j<=kでj番目に最小になる可能性があることです。 kの前のセルは空です。

次に、削除した要素を追跡し、kよりも小さい要素がいくつ削除されたかを知るだけで十分です。せいぜいO（log n）でこれをどのように間に合わせるのですか？範囲ツリーまたは同様のタイプのデータ構造を使用する。範囲ツリーは、整数を追加してから、 XとYの間のすべての整数を照会できる構造です。したがって、アイテムを削除するときはいつでも、範囲ツリーに追加するだけです。そして、k番目に小さい要素を探しているときは、削除された0からkまでのすべての整数に対してクエリを実行します。そのデルタを言うが削除されている場合、k番目の要素はT [k+delta]になります。

わずかな問題が2つあり、修正が必要です。

  • 範囲ツリーは時間O（log n）の範囲を返しますが、範囲内の要素の数をカウントするには、範囲内の各要素をウォークスルーする必要があるため、時間O（D）が追加されます。ここでDは範囲内のアイテムを削除しました。これを取り除くには、範囲ツリー構造を変更して、各ノードでサブツリー内の個別の要素の数を追跡する必要があります。このカウントを維持するのにかかる費用はO（log n）のみであり、全体的な複雑さには影響しません。これを行うのはかなり簡単な変更です。

  • 実際には、クエリを1つだけ作成しても機能しません。実際、1からkの範囲でデルタ削除された要素を取得する場合は、k+1からk+deltaの範囲で削除された要素がないことを確認する必要があります。完全なアルゴリズムは、以下の内容に沿ったものになります。

KthSmallest(T,k) := {
  a = 1;  b = k;  delta

  do {
    delta = deletedInRange(a, b)
    a = b + 1
    b = b + delta
  while( delta > 0 )

  return T[b]
}

この操作の正確な複雑さは、削除をどの程度正確に行うかによって異なりますが、要素がランダムに均一に削除される場合、反復回数はかなり少なくする必要があります。

于 2012-05-08T22:59:23.253 に答える
0

heapsを調べます。挿入と削除は O(log n) で、最小要素のピークは O(1) です。ただし、K 番目の要素のピークまたは取得は、O(log n) になります。

EDITED：アミットが述べたように、検索はただのぞき見よりも高価です

于 2012-05-07T07:33:26.257 に答える
0

これはおそらく不可能です。ただし、平衡二分木に特定の変更を加えて、O(log n) の k 番目の要素を取得できます。

詳細については、ウィキペディアをご覧ください。

于 2012-05-07T08:02:39.377 に答える
0

Indexible Skip リストは、あなたが望むことを行う (閉じる) ことができるかもしれません: http://en.wikipedia.org/wiki/Skip_lists#Indexable_skiplist

ただし、いくつかの注意事項があります。

  1. これは確率的なデータ構造です。つまり、すべての操作で必ずしも O(log N) になるとは限りません
  2. インデックス作成では O(1) にはなりません。O(log N) だけです。
  3. RNG の速度とトラバース ポインターの速度によっては、配列に固執して削除のコストが高くなることに対処するよりも、パフォーマンスが低下する可能性があります。

ほとんどの場合、これに沿った何かが、目標を達成するためにできる「最善」の方法です。

于 2012-05-07T08:13:06.370 に答える