3

時間計算量が O(log n) のセットの中央値を削除するにはどうすればよいでしょうか? アイデア？

4

9 に答える 9

18

セットがソートされている場合、中央値を見つけるには O(1) 個のアイテムを取得する必要があります。項目が任意の順序になっている場合、項目の大部分を調べずに中央値を確実に特定することはできません。すべてではないがほとんどの項目を調べた場合、中央値がある範囲内にあることが保証されます [リストに重複が含まれている場合、上限と下限が一致する可能性があります]。リスト内のアイテムは、O(n) 個のアイテムの取得を意味します。

完全に順序付けされていないが、特定の順序付け関係がわかっているコレクションに情報がある場合、必要な時間は、既知の順序付けの性質に応じて、O(1) から O(n) 項目の取得の間のどこかを必要とする場合があります。関係。

于 2010-09-03T00:46:24.760 に答える
5

ソートされていないリストの場合、中央値の位置にある要素がわかるまで、O（n）部分ソートを繰り返し実行します。ただし、これは少なくともO（n）です。

ソートされている要素に関する情報はありますか？

于 2010-09-03T01:16:00.097 に答える
4

一般的なソートされていないセットの場合、O(n) 時間よりも短い時間で中央値を確実に見つけることは不可能です。O(1) でソートされたセットの中央値を見つけることができます。または、O(n log n) 時間でセットを簡単にソートしてから、O(1) で中央値を見つけて、O(n logn n) を与えることができます。アルゴリズム。または、最後に、ソートの代わりにパーティショニングによって機能し、O(n) のパフォーマンスを実現できる、より巧妙な中央値選択アルゴリズムがあります。

しかし、セットに特別なプロパティがなく、前処理ステップが許可されていない場合、すべての要素を少なくとも 1 回調べる必要があるという単純な事実によって、O(n) を下回ることはありません。正しい。

于 2010-09-03T01:21:43.583 に答える
4

TreeSet に基づく Java のソリューションは次のとおりです。

public class SetWithMedian {
    private SortedSet<Integer> s = new TreeSet<Integer>();
    private Integer m = null;

    public boolean contains(int e) {
        return s.contains(e);
    }
    public Integer getMedian() {
        return m;
    }
    public void add(int e) {
        s.add(e);
        updateMedian();
    }
    public void remove(int e) {
        s.remove(e);
        updateMedian();
    }
    private void updateMedian() {
        if (s.size() == 0) {
            m = null;
        } else if (s.size() == 1) {
            m = s.first();
        } else {
            SortedSet<Integer> h = s.headSet(m);
            SortedSet<Integer> t = s.tailSet(m + 1);
            int x = 1 - s.size() % 2;
            if (h.size() < t.size() + x)
                m = t.first();
            else if (h.size() > t.size() + x)
                m = h.last();
        }
    }
}

中央値の削除 (つまり、"s.remove(s.getMedian())") には O(log n) の時間がかかります。

編集：コードを理解するのを助けるために、クラス属性の不変条件は次のとおりです。

private boolean isGood() {
    if (s.isEmpty()) {
        return m == null;
    } else {
        return s.contains(m) && s.headSet(m).size() + s.size() % 2 == s.tailSet(m).size();
    }
}

人間が読める形式:

  • セット "s" が空の場合、"m" は null でなければなりません。
  • セット "s" が空でない場合は、"m" が含まれている必要があります。
  • x を厳密に「m」未満の要素数とし、y を「m」以上の要素数とする。次に、要素の総数が偶数の場合、x は y と等しくなければなりません。それ以外の場合、x+1 は y と等しくなければなりません。
于 2010-09-03T02:03:44.833 に答える
4

赤黒木を試してみてください。静かにうまく動作し、バイナリ検索で ur log(n) が得られます。log(n) の削除および挿入時間もあり、リバランスも log(n) で行われます。

于 2012-06-24T22:58:59.677 に答える
3

前の回答で述べたように、データ構造のすべての要素に触れずに中央値を見つける方法はありません。探しているアルゴリズムを順番に実行する必要がある場合、最善の方法は O(n) です。決定論的選択アルゴリズム (median-of-medians) または BFPRT アルゴリズムは、O(n) の最悪のケースで問題を解決します。詳細については、こちらをご覧ください: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

ただし、中央値アルゴリズムの中央値は、並列にする O(n) よりも高速に実行することができます。分割統治の性質により、アルゴリズムは「簡単に」並列化できます。たとえば、入力配列を 5 の要素に分割する場合、サブ配列ごとにスレッドを起動し、並べ替えて、そのスレッド内の中央値を見つけることができます。このステップが終了すると、スレッドが結合され、新しく形成された中央値の配列を使用してアルゴリズムが再度実行されます。

このような設計は、非常に大きなデータ セットでのみ有益であることに注意してください。スレッドの生成とそれらのマージによる追加のオーバーヘッドにより、小さなセットでは実行できなくなります。これには少しの洞察があります: http://www.umiacs.umd.edu/research/EXPAR/papers/3494/node18.html

漸近的に高速なアルゴリズムを見つけることができますが、日常的に使用するには実用的ではないことに注意してください。あなたの最善の策は、すでに述べた順次中央値の中央値アルゴリズムです。

于 2013-05-16T23:27:50.657 に答える
2

マスターヨーダのランダム化アルゴリズムは、もちろん、他のアルゴリズムと同様に最小の複雑さはn、予想される複雑さはn（log nではない）、クイックソートのように最大の複雑さはnの2乗です。それでもとても良いです。

実際には、「ランダムな」ピボットの選択は、初期の配列要素が十分にランダムであることがわかっている（たとえば、個別の値のランダムな順列、または独立して同じように分布している）か、入力値のおおよそまたは正確に既知の分布。

于 2011-10-11T15:18:16.493 に答える
2

私は、予想される O(n) の時間計算量を持つ 1 つのランダム化アルゴリズムを知っています。

アルゴリズムは次のとおりです。

入力: n 個の数値の配列 A[1...n] [一般性を失うことなく、n は偶数であると仮定できます]

出力: ソートされた配列の n/2 番目の要素。

アルゴリズム ( A[1..n] 、k = n/2):

ピボットを選択 - 1...n から普遍的にランダムに p

配列を 2 つの部分に分割:

L - 要素 <= A[p] を持つ

R - 要素 > A[p] を持つ

if(n/2 == |L|) A[|L| + 1] は中央値のストップです

if( n/2 < |L|) (L, k) の再帰

そうでなければ (R, k - (|L| + 1) を再呪する

複雑さ: O( n) 証明はすべて数学的です。1ページ長い。興味がある場合は、私に ping を送信してください。

于 2010-09-05T01:52:57.953 に答える
0

rwong の回答を拡張するには: コード例を次に示します。

// partial_sort example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


int main () {
  int myints[] = {9,8,7,6,5,4,3,2,1};
  vector<int> myvector (myints, myints+9);
  vector<int>::iterator it;

  partial_sort (myvector.begin(), myvector.begin()+5, myvector.end());

  // print out content:
  cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}

出力: myvector の内容: 1 2 3 4 5 9 8 7 6

真ん中の要素が中央値になります。

于 2012-06-24T22:50:44.727 に答える