Изменения

{{ОпределениеАлгоритм был разработан Мануэлем Блюмом (Manuel Blum), Робертом Флойдом (Robert Floyd), Воганом Рональдом Праттом (Vaughan Ronald Pratt), Роном Ривестом (Ron Rivest), Робертом Тарьяном (Robert Tarjan).|definition==Идея алгоритма=='''Этот алгоритм является модификацией алгоритма [[Поиск k-ой порядковой статистики|поиска k-ой порядковой статистики]]. Важное отличие заключается в том, что время работы алгоритма в наихудшем случае — <tex>O(n)</tex>, где <tex>kn</tex>-ой порядковой статистикой— количество элементов в множестве. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' набора элементов линейно упорядоченного множества называется хорошее разбиение массива. Алгоритм выбирает такой его рассекающий элемент, который является что количество чисел, которые меньше рассекающего элемента, не менее <tex>k\dfrac{3n}{10}</tex>-ым элементом набора в порядке сортировки. Элементов же больших опорного элемента, также не менее <tex>\dfrac{3n}{10}== Историческая справка ==</tex>. Благодаря этому алгоритм работает за линейное время в любом случае.

'''Алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна''' == Описание алгоритма ==#Все <tex>n</tex> элементов входного массива разбиваются на группы по пять элементов, в последней группе будет <tex>n \bmod 5</tex> элементов. Эта группа может оказаться пустой при <tex>n</tex> кратным <tex>5</tex>.#Сначала сортируется каждая группа, затем из каждой группы выбирается медиана.#Путем рекурсивного вызова шага определяется медиана <tex>x</tex> из множества медиан (BFPRT-алгоритмверхняя медиана в случае чётного количества) создан Мануэлем Блюмом, найденных на втором шаге. Найденный элемент массива <tex>x</tex> используется как рассекающий (Manuel Blumза <tex>i</tex> обозначим его индекс).#Массив делится относительно рассекающего элемента <tex>x</tex>.#Если <tex>i = k</tex>, Робертом Флойдомто возвращается значение <tex>x</tex>. Иначе запускается рекурсивно поиск элемента в одной из частей массива: <tex>k</tex>-ой статистики в левой части при <tex>i > k</tex> или <tex>(Robert Floydk - i - 1)</tex>-ой статистики в правой части при <tex>i < k</tex> === Пример работы алгоритма ===Рассмотрим работу алгоритма на массиве из <tex> 25 </tex> элементов, обозначенных кружками. На вход подается массив, разобьем элементы на группы по 5 элементов.Отсортируем элементы каждой группы и выберем медианы. Полученные медианы групп отмечены белыми кружками. [[Файл:поиск.png| 300px]]  Рекурсивно вызовемся от медиан групп и получим рассекающий элемент. На рисунке он обозначен белым кружком, внутри которого изображен символ <tex> x </tex>.  [[Файл:поиск2.png| 300px]] На рисунке обозначены закрашенные области, в левом верхнем и в правом нижнем углах. В эти области попали все элементы, которые точно меньше или больше рассекающего элемента, соответственно. В каждой области по <tex> 8 </tex> элементов, всего же в массиве <tex> 25 </tex>, Воганом Рональдом Праттомто есть мы получили хорошее (Vaughan Ronald Prattто есть соответствующее нашему утверждению)разбиение массива относительно опорного элемента, Роном Ривестом(Ron Rivest) так как <tex> 8 > </tex> <tex>\dfrac{3 \cdot 25}{10}</tex>. Теперь докажем, что алгоритм также хорошо выбирает опорный элемент и Рональдом Тарьяном(Robert Tarjan) в 1973 годуобщем случае. 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>\dfrac{3n}{10}</tex>.

== Описание алгоритма ==Разбиваем наш массив на группы Проведя аналогичные рассуждения для элементов, которые меньше по 5 элементов(на самом деле можно разбивать и на другое нечетное количество элементов больших 5). Затем в каждой группе находим средний величине, чем рассекающий элемент(медиану)<tex>x</tex>, это можно сделать любой сортировкой. И запускаем рекурсивно этот алгоритм от медиан. Тем самым мы найдем средний элемент среди медианполучим, то есть медиану медиан. Эту медиану медиан выберем рассекающим элементом для поиска что как минимум <tex>k\dfrac{3n}{10}</tex>-го элемента. Далее разбиваем массив на две части: слева от рассекающего элемента числа меньшие негоменьше, а справа - числа больше рассекающего элемента или равные ему. И рекурсивно запускаем наш алгоритм от той части массива, в котором будет лежать чем элемент <tex>kx</tex>-й элемент.Теперь проведем анализ времени работы алгоритма. [[Файл:поиск5.png| 300px]]

Пусть <tex>T(n)</tex> — время работы алгоритма для <tex>n</tex> элементов, тогда она меньшеоно не больше, чем <tex>Cn</tex> - время сумма:# времени работы, на сортировку групп, и разбиение по рассекающему элементу. Плюс время сумма время , то есть <tex>Cn</tex>;# времени работы для поиска медианы медиан, то есть <tex>T</tex><tex>\left(\fracdfrac{n}{5}\right)</tex>. И кроме того время ;# времени работы для поиска <tex>k</tex>-го элемента в одной из двух частей массива, то есть <tex>T(ks)</tex>, где <tex>ks</tex>, — количество элементов в этой части, но . Но <tex>ks</tex> не превосходит <tex>\fracdfrac{7n}{10}</tex>, так как чисел меньше , меньших рассекающего элемента , не менее <tex>\fracdfrac{3n}{10}</tex> - — это <tex>\fracdfrac{n}{10}</tex> медиан меньшие , меньших медианы медиан , плюс не менее <tex>\fracdfrac{2n}{10}</tex> элементов меньшие , меньших этих медиан, с . С другой стороны , чисел , больших рассекающего элемента , так же не менее <tex>\fracdfrac{3n}{10}</tex>, следовательно <tex> s \leqslant </tex> <tex>\dfrac{7n}{10}</tex>, то есть в худшем случае <tex> k s = </tex> <tex>\fracdfrac{7n}{10}</tex>.

<tex>T(n) \le leqslant T</tex><tex>\left(\fracdfrac{n}{5}\right) </tex><tex> + T</tex><tex>\left(\fracdfrac{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>\left(\dfrac{n}{5}\right)</tex> <tex> \leqslant 10C </tex><tex>\dfrac{n}{5}</tex> <tex> = 2Cn</tex> и <tex> T</tex><tex>\left(\dfrac{7n}{10}\right)</tex> <tex> \leqslant 10C </tex><tex>\dfrac{7n}{10}</tex> <tex> = 7Cn</tex>, тогда<tex>T(n) \leqslant T</tex><tex>\left(\dfrac{n}{5}\right)</tex> <tex> + T</tex><tex>\left(\dfrac{7n}{10}\right)</tex> <tex> + Cn = 2Cn + 7Cn + Cn = 10Cn \Rightarrow T(n) \leqslant 10Cn</tex>

Покажем, что для всех Так как <tex> T(n ) \leqslant 10Cn </tex> выполняется неравенство , то время работы алгоритма <tex>TO(n) \le 10Cn </tex>.

Докажем по индукции==Источники инфомации==# Очевидно* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, что для малых <tex> n </tex> выполняется неравенство <tex>T(n) \le 10Cn </tex> # Тогда по предположению индукции <tex>T(\fracК. '''Алгоритмы: построение и анализ''' {n}{5---}) \le 10C(\frac{n}Вильямс, 2013. {5}) = 2Cn</tex> и <tex> T(\frac{10n---}{7}) \le 10C(\frac1328 с. {7n}{10---}) = 7Cn</tex>, тогда<tex>T(n) \le T(\frac{n}{ISBN 978-5}) + T(\frac{7n}{10}) + Cn = 2Cn + 7Cn + Cn = 10Cn \Rightarrow T(n) \le 10Cn<-8459-1794-2* [http://en.wikipedia.org/wiki/tex>BFPRT#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm Wikipedia — Selection algorithm]

== Ссылки ==[[Категория: Дискретная математика и алгоритмы]][[Категория: Сортировки]]* [http[Категория://en.wikipedia.org/wiki/BFPRT#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm Selection algorithm — WikipediaДругие сортировки]]