Медианный алгоритм в O (log n)

Question

Как мы можем удалить медиану множества с временной сложностью O (log n)?Какая-то идея?

Answer 1

Если набор отсортирован, для поиска медианы требуется O (1) поиск предметов. Если элементы расположены в произвольной последовательности, невозможно будет точно определить медиану, не изучив большинство элементов. Если вы изучили большинство, но не все элементы, это позволит гарантировать, что медиана будет находиться в некотором диапазоне [если список содержит дубликаты, верхняя и нижняя границы могут совпадать], но при этом изучается большинство элементы в списке подразумевают O (n) поиска элементов.

Если в коллекции имеется информация, которая не полностью упорядочена, но где известны определенные отношения упорядочения, то для требуемого времени может потребоваться где-то между O (1) и O (n) извлечением элементов в зависимости от характера известное отношение порядка.

Answer 2

Для несортированных списков многократно выполняйте O (n) частичную сортировку , пока не станет известен элемент, расположенный в средней позиции. Это как минимум O (n) , хотя.

Есть ли какая-либо информация о сортируемых элементах?

Answer 3

Попробуйте Красно-черное дерево .Он должен работать тихо и хорошо, и при бинарном поиске вы получите ur log (n).Также имеется время удаления и вставки журнала (n), а в журнале (n) также выполняется ребалансировка.

Answer 4

Вот решение на Java, основанное на TreeSet:

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» должен быть нулевым.
• Если набор «s» не пустой, то он должен содержать «m».
• Пусть xбыть количеством элементов, строго меньшим, чем «m», и пусть y будет количеством элементов, большим или равным «m».Тогда, если общее количество элементов четное, x должно быть равно y;в противном случае x + 1 должен быть равен y.

Answer 5

Для общего несортированного набора невозможно надежно найти медиану за время, превышающее O (n).Вы можете найти медиану отсортированного набора в O (1), или вы можете тривиально самостоятельно отсортировать набор за O (n log n), а затем найти медиану в O (1), дав O (n logn n)алгоритм.Или, наконец, есть более умные алгоритмы выбора медианы, которые могут работать путем разделения вместо сортировки и обеспечивать производительность O (n).

Но если набор не имеет специальных свойств и вам не разрешен какой-либо шаг предварительной обработки, вы никогда не будете опускаться ниже O (n) из-за того простого факта, что вам нужно будет проверить все элементы как минимумодин раз, чтобы убедиться, что медиана верна.

Answer 6

Как упоминалось в предыдущих ответах, невозможно найти медиану, не касаясь каждого элемента структуры данных.Если алгоритм, который вы ищете, должен выполняться последовательно, то лучшее, что вы можете сделать, это O (n).Детерминированный алгоритм выбора (медиана медиан) или алгоритм 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

Обратите внимание, что вы можете найти асимптотически более быстрые алгоритмы, но они не достаточно практичны для повседневного использования.Ваша лучшая ставка - это уже упомянутый последовательный алгоритм медианы медиан.

Answer 7

Рандомизированный алгоритм Мастера Йоды, конечно, имеет минимальную сложность n, как и любую другую, ожидаемую сложность n ( не логарифм n ) и максимальную сложность n в квадрате, как быстрая сортировка.Это все еще очень хорошо.

На практике «случайный» выбор поворота иногда может быть фиксированным местоположением (без использования ГСЧ), поскольку известно, что начальные элементы массива достаточно случайны (например, случайная перестановка различных значений или независимая ираспределяется одинаково) или выводится из приблизительного или точно известного распределения входных значений.

Answer 8

Я знаю один алгоритм рандомизации с временной сложностью O (n) в ожидании.

Вот алгоритм:

Ввод: массив из n чисел A [1 ... n] [без ограничения общности мы можем предположить, что n четно]

Вывод: n / 2-й элемент в отсортированном массиве.

Алгоритм (A [1..n], k = n / 2):

Выберите точку поворота - p универсально случайным образом от 1 ... n

Разделенный массив на 2 части:

L - имеющий элемент <= A [p] </p>

R - имеющий элемент> A [p]

если (n / 2 == | L |) A [| L | + 1] - медианная остановка

если (n / 2 <| L |) повторно проклясть (L, k) </p>

еще раз прокляните на (R, k - (| L | + 1)

Сложность: O (n) доказательство все математическое. Одна страница длиной. Если тебе интересно пингуй меня.

Answer 9

Чтобы расширить ответ Руонга: Вот пример кода

// 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

Элемент в середине будет медианой.