Найти медиану несортированного массива за время

45

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

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

Luv
источник
10
ru.wikipedia.org/wiki/Selection_algorithm
Юкка Суомела
1
@JukkaSuomela Почему бы не сделать этот быстрый и простой ответ (с идеальным кратким объяснением одного из таких алгоритмов)?
Рафаэль
2
Обратите внимание на соответствующую мета-дискуссию ; Оказывается, простой поиск в Интернете приводит к ответу на этот вопрос.
Рафаэль

Ответы:

45

Это особый случай алгоритма выбора, который может найти й наименьший элемент массива с половине размера массива. Существует реализация, которая является линейной в худшем случае.кkk

Общий алгоритм выбора

Сначала давайте рассмотрим алгоритм, find-kthкоторый находит й наименьший элемент массива:k

find-kth(A, k)
  pivot = random element of A
  (L, R) = split(A, pivot)
  if k = |L|+1, return pivot
  if k ≤ |L|  , return find-kth(L, k)
  if k > |L|+1, return find-kth(R, k-(|L|+1))

Функция split(A, pivot)возвращает L,Rтаким образом, что все элементы Rбольше , чем pivotи Lвсе остальные (минус один вхождение pivot). Тогда все делается рекурсивно.

В среднем это но в худшем случае .O ( n 2 )O(n)O(n2)

Линейный наихудший случай: алгоритм медианы медиан

Лучшей осью является медиана всех медиан подмассивов Aразмера 5 с использованием вызова процедуры для массива этих медиан.

find-kth(A, k)
  B = [median(A[1], .., A[5]), median(A[6], .., A[10]), ..]
  pivot = find-kth(B, |B|/2)
  ...

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

Обратите внимание, что в большинстве случаев использование случайного поворота происходит быстрее.

jmad
источник
Это 5стандартный размер ? Что если размер А меньше 5?
Джаеш
Для любого фиксированного n сложность постоянна, если она не бесконечна. Таким образом, вы можете использовать любой действительный алгоритм с конечной сложностью для такого особого случая, даже если он был O (2 ^ n). Для фиксированного n (т.е. не более 4 в нашем случае) сложность составляет не более O (2 ^ 4) = O (1).
v6ak
3
По первому алгоритму: return A[k]неверно (если Aне отсортировано, что сделает алгоритм спорным). Если splitслучилось, что разделить так A, что k = |L| + 1вы все еще не знаете, где находится kй элемент. Ваш базовый случай - это когда |A| = 1вам еще нужно сделать один из двух рекурсивных вызовов.
wcochran
2
@NickCaplinger исправлено с помощью web.archive.org
jmad
1
Разве это не худший случай для универсального алгоритма выбора O (NlogN)? Даже если рекурсивных вызовов листьев только 10% из массива после каждого вызова, то она по - прежнему логарифм в основе 10
Октавиан
6

Для этого существует рандомизированный алгоритм Монте-Карло. Это описано в [MU2017]. Это линейный алгоритм времени, который не дает решения с вероятностью не более . Как обсуждалось в [MU2017], он значительно проще, чем детерминированный алгоритм , и дает меньший постоянный коэффициент в линейном времени работы. О ( п )n1/4O(n)

Основная идея алгоритма заключается в использовании выборки. Мы должны найти два элемента, которые расположены близко друг к другу в отсортированном порядке массива и имеют медиану, лежащую между ними. См. Ссылку [MU2017] для полного обсуждения.


[MU2017] Михаэль Митценмахер и Эли Упфал. «Вероятность и вычисления: рандомизация и вероятностные методы в алгоритмах и анализе данных», глава 3, страницы 57–62. Издательство Кембриджского университета, второе издание, 2017.

ZDM
источник