Чтобы найти медиану несортированного массива, мы можем сделать минимальную кучу за времени для элементов, а затем мы можем извлечь один за другим элементов, чтобы получить медиану. Но этот подход занял бы времени.
Можем ли мы сделать то же самое некоторым способом за раз? Если мы можем, то как?
Ответы:
Это особый случай алгоритма выбора, который может найти й наименьший элемент массива с половине размера массива. Существует реализация, которая является линейной в худшем случае.кk k
Общий алгоритм выбора
Сначала давайте рассмотрим алгоритм,k
find-kth
который находит й наименьший элемент массива:Функция
split(A, pivot)
возвращаетL,R
таким образом, что все элементыR
больше , чемpivot
иL
все остальные (минус один вхождениеpivot
). Тогда все делается рекурсивно.В среднем это но в худшем случае .O ( n 2 )O(n) O(n2)
Линейный наихудший случай: алгоритм медианы медиан
Лучшей осью является медиана всех медиан подмассивов
A
размера 5 с использованием вызова процедуры для массива этих медиан.Это гарантирует во всех случаях. Это не так очевидно. Эти слайды PowerPoint полезны как для объяснения алгоритма, так и для сложности.O(n)
Обратите внимание, что в большинстве случаев использование случайного поворота происходит быстрее.
источник
5
стандартный размер ? Что если размер А меньше 5?return A[k]
неверно (еслиA
не отсортировано, что сделает алгоритм спорным). Еслиsplit
случилось, что разделить такA
, чтоk = |L| + 1
вы все еще не знаете, где находитсяk
й элемент. Ваш базовый случай - это когда|A| = 1
вам еще нужно сделать один из двух рекурсивных вызовов.Для этого существует рандомизированный алгоритм Монте-Карло. Это описано в [MU2017]. Это линейный алгоритм времени, который не дает решения с вероятностью не более . Как обсуждалось в [MU2017], он значительно проще, чем детерминированный алгоритм , и дает меньший постоянный коэффициент в линейном времени работы. О ( п )n−1/4 O(n)
Основная идея алгоритма заключается в использовании выборки. Мы должны найти два элемента, которые расположены близко друг к другу в отсортированном порядке массива и имеют медиану, лежащую между ними. См. Ссылку [MU2017] для полного обсуждения.
[MU2017] Михаэль Митценмахер и Эли Упфал. «Вероятность и вычисления: рандомизация и вероятностные методы в алгоритмах и анализе данных», глава 3, страницы 57–62. Издательство Кембриджского университета, второе издание, 2017.
источник