Изменения
Нет описания правки
На вход подается массив, разобьем элементы на группы по 5 элементов.
Отсортируем элементы каждой группы и выберем медианы. Вызовемся рекурсивно Полученные медианы групп отмечены белыми кружками. [[Файл:поиск.png| 300px]] Рекурсивно вызовемся от медиангрупп и получим рассекающий элемент. На рисунке он обозначен белым кружком, внутри которого изображен символ <tex> x </tex>.
Проведя аналогичные рассуждения для элементов, которые меньше по величине, чем рассекающий элемент <tex>x</tex>, мы получим, что как минимум <tex>\dfrac{3n}{10}</tex> меньше, чем элемент <tex>x</tex>. Теперь проведем анализ времени работы алгоритма.
[[Файл:поиск5.png| 300px]]
== Анализ времени работы алгоритма ==
Пусть <tex>T(n)</tex> - — время работы алгоритма для <tex>n</tex> элементов, тогда оно не больше, чем сумма:
# времени работы на сортировку групп и разбиение по рассекающему элементу, то есть <tex>Cn</tex>;
# времени работы для поиска медианы медиан, то есть <tex>T</tex><tex>\left(\fracdfrac{n}{5}\right)</tex>;# времени работы для поиска <tex>k</tex>-го элемента в одной из двух частей массива, то есть <tex>T(s)</tex>, где <tex>s</tex>- — количество элементов в этой части. Но <tex>s</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 \le leqslant </tex> <tex>\fracdfrac{7n}{10}</tex>, то есть в худшем случае <tex> 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) \le leqslant 10Cn </tex>.
Докажем по индукции:
# ОчевидноПредположим, что для малых наше неравенство <tex> T(n ) \leqslant 10Cn </tex> выполняется неравенство при малых <tex>T(n) \le 10Cn </tex> , для некоторой достаточно большой константы <tex> C </tex>. # Тогда, по предположению индукции, <tex>T</tex><tex>\left(\fracdfrac{n}{5}\right) </tex> <tex> \le leqslant 10C(</tex><tex>\fracdfrac{n}{5}) </tex> <tex> = 2Cn</tex> и <tex> T</tex><tex>\left(\fracdfrac{7n}{10}\right) </tex> <tex> \le leqslant 10C(</tex><tex>\fracdfrac{7n}{10}) </tex> <tex> = 7Cn</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 = 2Cn + 7Cn + Cn = 10Cn \Rightarrow T(n) \le leqslant 10Cn</tex>
Так как <tex>T(n) \le 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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Другие сортировки]]