1

次の問題の解決策を考えています: 整数の大きな配列 (さらに難しい場合は整数のストリーム) があり、その配列を中央値の配列に変換したいのですが、その位置は配列の中央値に対応しています [ 0..i].

さて、私の力ずくのアプローチは、サブアレイごとに並べ替えてから、中央の要素を選択することです。これは O(n^2 log n) で、各 n サブアレイは N log N 時間でソートする必要があります。おそらく、何らかのカウントメカニズムを使用して時間を N^2 に下げることができますが、N^2 で実行できるのが最善でしょうか?

4

3 に答える 3

3

赤黒木など、すでにソートされている木のような構造に単一の項目を挿入するには、O(log n ) が必要です。すべてのノードの子孫の数を維持する場合、中央値を見つけることも O(log n ) で行うことができます。ストリームのすべてのn要素に対してこれを行うと、O( n log n ) アルゴリズムが得られます。

データ構造と中央値の計算は次のようになります。

struct TreeNode {
  enum { RED, BLACK } color;
  size_t numElements;
  int value;
  TreeNode* left, right;
} *root;

TreeNode* treeSelect(TreeNode *top, size_t count) {
  if (top->left != NULL) {
    if (count < top->left->numElements)
      return treeSelect(top->left, count)
    count -= top->left->numElements;
  }
  if (count == 0)
    return top;
  return treeSelect(top->right, count - 1);
}

TreeNode* treeMedian() {
  return treeSelect(root, root->numElements / 2);
}

他の操作は通常、赤黒木に使用される操作ですが、ノードの削除にはスキップできます。重複する要素で機能するように調整できます。ここでの原則は、挿入する要素が現在のノードの要素と等しい場合、どの子ツリーにも挿入できるということです。また、ツリーのバランスをとるときは、重複キーの順序を維持する必要があります。これにより、接続されたサブツリーの順序も維持できます。しかし、私が何かを見逃していない限り、いずれの場合でも値の比較なしでバランスを取ることができるので、重複を挿入したら完了です。非常に多くの重複値が予想される場合は、各ノードにカウンターを使用して、代わりにマルチマップのようなアプローチを使用できます。

于 2013-01-11T11:56:43.580 に答える
0

O(nlogn)これは、次のアプローチで実行できます。

データのストリームを維持するには、スキップ リスト (または B+ ツリー) を使用します。
また、現在の中央値へのポインターを維持します。

各反復で、ノードの数をn(到着したばかりの要素を挿入する前に)、中央値 (値)mを 、表示される新しい値を としますx。

  1. xスキップリストに挿入
  2. If n%2 ==0(中央値のインデックスが増加する必要があります):
    if x < m.value: 変更の必要がない場合、インデックスmも増加する
    else: 設定するm <- m.next
  3. else: (中央値のインデックスは同じままである必要があります)
    if x < m.value: set m <- m.previous//m のインデックスが増加したため、
    else: 変更は必要ありません。// m のインデックスは増加しませんでした
  4. m.value次の要素の中央値です

前/次の検索はO(1)、挿入xはO(logn)- 全体の複雑さにはO(nlogn)追加O(n)のスペースがあります。

注: ストリームに重複する要素を含めることができる場合は特別な注意を払う必要があり、スキップリストはそれに対して決定論的な動作を持つ必要があります。つまり、常に最後の可能なインデックスを挿入します。

于 2013-01-11T12:00:41.917 に答える
0

AVL や Splay などの高速 BST を使用します。各ノードが時間内にそのサブツリーの中央値を取得できるように、構造を変更するだけですlog N。特に、ツリー内のすべてのアイテムの中央値を取得できます。

今、あなたはこのようなことをしています:

Create empty BST
foreach n in stream:
    Insert n to BST
    Get median from BST.root
于 2013-01-11T12:31:40.607 に答える