Изменения

{{ОпределениеАлгоритм был разработан Мануэлем Блюмом (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Сортировки]]* [http[Категория://people.csail.mit.edu/rivest/BlumFloydPrattRivestTarjan-TimeBoundsForSelection.pdf Time Bounds for Selection by Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Journal of Computer and System Sciences 7,4 August 1973, 448—460Другие сортировки]]