Вопрос по heap, median, algorithm – Нахождение медианы несортированного массива

42

Чтобы найти медиану несортированного массива, мы можем сделать минимальную кучу за O (nlogn) времени для n элементов, а затем мы можем извлечь один за другим n / 2 элемента, чтобы получить медиану. Но этот подход занял бы O (nlogn) время.

Можем ли мы сделать то же самое некоторым способом за O (n) раз? Если мы можем, пожалуйста, скажите или предложите какой-нибудь метод.

Имейте в виду, что если он принимает O (nlogn), то вы можете просто отсортировать массив и разделить индекс на 2. Zombies
сборка кучи занимает O (n) времени, а не O (nlogn) JerryGoyal

Ваш Ответ

6   ответов
0

обратитесь к статистике K-го порядка (рандомизированные алгоритмы).

0

Median-of-Medians теоретически равен o (N), но на практике он не используется, потому что накладные расходы по поиску «хороших» шарниры делает это слишком медленно.
http://en.wikipedia.org/wiki/Selection_algorithm

Вот исходный код Java для алгоритма быстрого выбора, чтобы найти k-й элемент в массиве:

/**
 * 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;
}

Я не включил источник методов сравнения и обмена, поэтому легко изменить код для работы с Object [] вместо double [].

На практике вы можете ожидать, что приведенный выше код будет o (N).

своп ???????????????
15

поскольку алгоритм «Медиана медиан» фактически решает эту проблему за O (n) раз. Я только хочу добавить, что эта проблема может быть решена за O (n) время также с помощью кучи. Построение кучи может быть выполнено за O (n) время с использованием восходящего. Взгляните на следующую статью для подробного объясненияСортировка кучи

Предположим, что в вашем массиве есть N элементов, вам нужно построить две кучи: MaxHeap, который содержит первые N / 2 элемента (или (N / 2) +1, если N нечетно), и MinHeap, который содержит оставшиеся элементы. Если N нечетно, то ваша медиана является максимальным элементом MaxHeap (O (1), получая максимум). Если N четное, то медиана равна (MaxHeap.max () + MinHeap.min ()) / 2, это также занимает O (1). Таким образом, реальной стоимостью всей операции является операция построения кучи, которая составляет O (n).

Кстати, этот алгоритм MaxHeap / MinHeap также работает, когда вы заранее не знаете количество элементов массива (если вам нужно решить ту же проблему для потока целых чисел, например). Подробнее о том, как решить эту проблему, можно узнать в следующей статье.Медиана Целочисленных потоков

Это O (n ^ 2) время худший случай, а не O (n). Когда ссылаются на сложность алгоритма Big O, без указания случая, обычно предполагается, что вы ссылаетесь на худшее время.
Почему это работает? Предположим, ваш массив [3, 2, 1]. Затем мы поместим первые 2 в максимальную кучу: [3, 2], таким образом, 3 будет корнем, так что 2, его дочерний элемент должен быть меньше его. И у нас будет [1] в мин куче. В соответствии с этим алгоритмом мы бы выбрали max (root) для maxHeap в качестве нашей медианы. Разве это не даст нам 3?
9

линейном (O(n)) Продолжительность. Вот реализация в Python:

import random

def partition(L, v):
    smaller = []
    bigger = []
    for val in L:
        if val < v: smaller += [val]
        if val > v: bigger += [val]
    return (smaller, [v], bigger)

def top_k(L, k):
    v = L[random.randrange(len(L))]
    (left, middle, right) = partition(L, v)
    # middle used below (in place of [v]) for clarity
    if len(left) == k:   return left
    if len(left)+1 == k: return left + middle
    if len(left) > k:    return top_k(left, k)
    return left + middle + top_k(right, k - len(left) - len(middle))

def median(L):
    n = len(L)
    l = top_k(L, n / 2 + 1)
    return max(l)
@akki Это ожидаемое значение & quot; линейное время из-за случайности. Интуиция заключается в том, что случайный индекс в среднем разделит список на список размером 1/4 и размером 3/4.
Как это линейно? Если я правильно понимаю, это реализация O (n ^ 2) в худшем случае.
35

Медиана Медиан алгоритм нахождения медианы несортированного массива за линейное время.

Это приблизительно, но должно работать довольно хорошо.
@KevinKostlan Это на самом деле не является приблизительным, это реальная медиана, и оно находит его в линейном времени. Обратите внимание, что после нахождения медианы медиан (которая гарантированно будет больше, чем, по крайней мере, 30% элементов и меньше, чем, по крайней мере, 30% элементов), вы разделяете массив с помощью этой оси. Затем вы возвращаетесь (при необходимости) в один из тех массивов, который не более чем на 70% размера исходного массива, чтобы найти реальную медиану (или в общем случае k-статистику).
10

Быстрый выбор работает в O (n), это также используется на этапе разбиения Quicksort.

Я не думаю, что быстрый выбор обязательно даст медиану ТОЛЬКО ОДИН пробег. Это зависит от вашего выбора.
К сожалению, быстрый выбор для поиска медианы в худшем случае займет O (n ^ 2). Это происходит, когда мы уменьшаем массив всего на 1 элемент в каждой итерации QuickSelect. Рассмотрим уже отсортированный массив, и мы всегда выбираем самый правый элемент как сводный. Я знаю, что это немного глупо, но это худшие случаи.

Похожие вопросы