Изменения
Нет описания правки
Алгоритм был разработан Мануэлем Блюмом (Manuel Blum), Робертом Флойдом (Robert Floyd), Воганом Рональдом Праттом (Vaughan Ronald Pratt), Роном Ривестом (Ron Rivest), Робертом Тарьяном (Robert Tarjan).
==Идея алгоритма==
Этот алгоритм является модификацией алгоритма [[Поиск k-ой порядковой статистики|поиска k-ой порядковой статистики]]. Важное отличие заключается в том, что время работы алгоритма в наихудшем случае — <tex>O(n)</tex>, где <tex>n</tex> — количество элементов в множестве. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива. Алгоритм выбирает такой рассекающий элемент, что количество чисел, которые меньше рассекающего элемента, не менее <tex dpi = "170">\fracdfrac{3n}{10}</tex>. Элементов же больших опорного элемента, также не менее <tex dpi = "170">\fracdfrac{3n}{10}</tex>. Благодаря этому алгоритм работает за линейное время в любом случае.
== Описание алгоритма ==
#Все <tex>n</tex> элементов входного массива разбиваются на группы по пять элементов, в последней группе будет <tex>n \bmod 5</tex> элементов. Эта группа может оказаться пустой при <tex>n</tex> кратных кратным <tex>5</tex>.
#Сначала сортируется каждая группа, затем из каждой группы выбирается медиана.
#Путем рекурсивного вызова шага определяется медиана <tex>x</tex> из множества медиан (верхняя медиана в случае чётного количества), найденных на втором шаге. Найденный элемент массива <tex>x</tex> используется как рассекающий (за <tex>i</tex> обозначим его индекс).
[[Файл:поиск2.png| 300px]]
На рисунке обозначены закрашенные области, в левом верхнем и в правом нижнем углах. В эти области попали все элементы, которые точно меньше или больше рассекающего элемента, соответственно. В каждой области по <tex> 8 </tex> элементов, всего же в массиве <tex> 25 </tex>, то есть мы получили хорошее (то есть соответствующее нашему утверждению) разбиение массива относительно опорного элемента, так как <tex> 8 > </tex> <tex dpi = "170">\fracdfrac{3 \cdot 25}{10}</tex>. Теперь докажем, что алгоритм также хорошо выбирает опорный элемент и в общем случае.
Cначала определим нижнюю границу для количества элементов, превышающих по величине рассекающий элемент <tex>x</tex>. В общем случае как минимум половина медиан, найденных на втором шаге, больше или равны медианы медиан <tex>x</tex>. Таким образом, как минимум <tex>\dfrac{n / }{10}</tex> групп содержат по <tex>3</tex> превышающих величину <tex>x</tex>, за исключение группы, в которой меньше <tex>5</tex> элементов и ещё одной группы, содержащей сам элемент <tex>x</tex>. Таким образом получаем, что количество элементов больших <tex>x</tex>, не менее <tex dpi = "170">\fracdfrac{3n}{10}</tex>.
Проведя аналогичные рассуждения для элементов, которые меньше по величине, чем рассекающий элемент <tex>x</tex>, мы получим, что как минимум <tex dpi = "170">\fracdfrac{3n}{10}</tex> меньше, чем элемент <tex>x</tex>. Теперь проведем анализ времени работы алгоритма.
[[Файл:поиск5.png| 300px]]
Пусть <tex>T(n)</tex> — время работы алгоритма для <tex>n</tex> элементов, тогда оно не больше, чем сумма:
# времени работы на сортировку групп и разбиение по рассекающему элементу, то есть <tex>Cn</tex>;
# времени работы для поиска медианы медиан, то есть <tex>T(</tex><tex dpi = "170">\fracleft(\dfrac{n}{5}</tex> <tex>\right) </tex>;# времени работы для поиска <tex>k</tex>-го элемента в одной из двух частей массива, то есть <tex>T(s)</tex>, где <tex>s</tex> — количество элементов в этой части. Но <tex>s</tex> не превосходит <tex dpi = "170">\fracdfrac{7n}{10}</tex>, так как чисел, меньших рассекающего элемента, не менее <tex dpi = "170">\fracdfrac{3n}{10}</tex> — это <tex dpi = "170">\fracdfrac{n}{10}</tex> медиан, меньших медианы медиан, плюс не менее <tex dpi = "170">\fracdfrac{2n}{10}</tex> элементов, меньших этих медиан. С другой стороны, чисел, больших рассекающего элемента, так же не менее <tex dpi = "170">\fracdfrac{3n}{10}</tex>, следовательно <tex> s \leqslant </tex> <tex dpi = "170">\fracdfrac{7n}{10}</tex>, то есть в худшем случае <tex> s = </tex> <tex dpi = "170">\fracdfrac{7n}{10}</tex>.
Тогда получаем, что
<tex>T(n) \leqslant T(</tex><tex dpi = "170">\fracleft(\dfrac{n}{5}\right)</tex><tex>) + T(</tex><tex dpi = "170">\fracleft(\dfrac{7n}{10}\right)</tex><tex>) + Cn </tex>
Покажем, что для всех <tex> n </tex> выполняется неравенство <tex>T(n) \leqslant 10Cn </tex>.
Докажем по индукции:
# Предположим, что наше неравенство <tex>T(n) \leqslant 10Cn </tex> выполняется при малых <tex> n </tex>, для некоторой достаточно большой константы <tex> C </tex>.
# Тогда, по предположению индукции, <tex>T(</tex><tex dpi = "170">\fracleft(\dfrac{n}{5}\right)</tex><tex>) \leqslant 10C </tex><tex dpi = "170">\fracdfrac{n}{5}</tex><tex> = 2Cn</tex> и <tex> T(</tex><tex dpi = "170">\fracleft(\dfrac{7n}{10}\right)</tex><tex>) \leqslant 10C </tex><tex dpi = "170">\fracdfrac{7n}{10}</tex><tex> = 7Cn</tex>, тогда<tex>T(n) \leqslant T(</tex><tex dpi = "170">\fracleft(\dfrac{n}{5}\right)</tex><tex>) + T(</tex><tex dpi = "170">\fracleft(\dfrac{7n}{10}\right)</tex><tex>) + Cn = 2Cn + 7Cn + Cn = 10Cn \Rightarrow T(n) \leqslant 10Cn</tex>
Так как <tex>T(n) \leqslant 10Cn </tex>, то время работы алгоритма <tex>O(n)</tex>
==ЛитератураИсточники инфомации==
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. '''Алгоритмы: построение и анализ''' {{---}} Вильямс, 2013. {{---}} 1328 с. {{---}} ISBN 978-5-8459-1794-2
* [http://en.wikipedia.org/wiki/BFPRT#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm Wikipedia — Selection algorithm — Wikipedia]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Поиск k-ой порядковой статистикиДругие сортировки]]
