algorithm - ソートされていない配列の中央値を見つける

Question

ソートされていない配列の中央値を見つけるには、n 要素に対して O(nlogn) 時間で最小ヒープを作成し、n/2 要素を 1 つずつ抽出して中央値を取得します。しかし、このアプローチには O(nlogn) 時間がかかります。

O(n)時間で何らかの方法で同じことができますか? 可能であれば、何らかの方法を教えてください。

Answer 1

Median of Mediansアルゴリズムを使用して、並べ替えられていない配列の中央値を線形時間で見つけることができます。

Answer 2

Quickselectは O(n) で機能します。これは、Quicksort のパーティション ステップでも使用されます。

Answer 3

これは O(n) の Quickselect Algorithm を使用して行うことができます。K 次統計 (ランダム化されたアルゴリズム) を参照してください。

Answer 4

ウィキペディアが言うように、Median-of-Medians は理論的には o(N) ですが、実際には使用されません。「適切な」ピボットを見つけるオーバーヘッドが遅すぎるためです。
http://en.wikipedia.org/wiki/Selection_algorithm

配列内の k 番目の要素を検索する Quickselect アルゴリズムの Java ソースを次に示します。

/**
 * Returns position of k'th largest element of sub-list.
 * 
 * @param list list to search, whose sub-list may be shuffled before
 *            returning
 * @param lo first element of sub-list in list
 * @param hi just after last element of sub-list in list
 * @param k
 * @return position of k'th largest element of (possibly shuffled) sub-list.
 */
static int select(double[] list, int lo, int hi, int k) {
    int n = hi - lo;
    if (n < 2)
        return lo;

    double pivot = list[lo + (k * 7919) % n]; // Pick a random pivot

    // Triage list to [<pivot][=pivot][>pivot]
    int nLess = 0, nSame = 0, nMore = 0;
    int lo3 = lo;
    int hi3 = hi;
    while (lo3 < hi3) {
        double e = list[lo3];
        int cmp = compare(e, pivot);
        if (cmp < 0) {
            nLess++;
            lo3++;
        } else if (cmp > 0) {
            swap(list, lo3, --hi3);
            if (nSame > 0)
                swap(list, hi3, hi3 + nSame);
            nMore++;
        } else {
            nSame++;
            swap(list, lo3, --hi3);
        }
    }
    assert (nSame > 0);
    assert (nLess + nSame + nMore == n);
    assert (list[lo + nLess] == pivot);
    assert (list[hi - nMore - 1] == pivot);
    if (k >= n - nMore)
        return select(list, hi - nMore, hi, k - nLess - nSame);
    else if (k < nLess)
        return select(list, lo, lo + nLess, k);
    return lo + k;
}

compare メソッドと swap メソッドのソースは含めていないので、double[] の代わりに Object[] で動作するようにコードを変更するのは簡単です。

実際には、上記のコードは o(N) であると予想できます。