Изменения

{{ОпределениеАлгоритм был разработан Мануэлем Блюмом (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</tex> <tex> mod</tex> <tex> \bmod 5</tex> элементов.Эта группа может оказаться пустой при <tex>n</tex> <tex>=</tex> кратным <tex>5</tex>.#Сначала сортируется каждая группа, затем выбираем медиану в из каждой из этих группгруппы выбирается медиана.#Путем рекурсивного вызова шага 1 определяется медиана <tex>x</tex> из множества медиан(верхняя медиана в случае чётного количества), найденных на втором шаге. Найденный элемент массива <tex>x</tex> — используется как рассекающий элемент, (за <tex>i</tex> — обозначим его индекс рассекающего элемента.Если медиан окажется четное количество, то на место рассекающего элемента будут претендовать две медианы, переменной <tex>x</tex> будет присвоено значение большей из этих двух медиан).#Делим массив Массив делится относительно рассекающего элемента <tex>x</tex>. Все элементы меньшие <tex>x</tex> будут находиться левее <tex>x</tex> в массиве и будут иметь меньший индекс и наоборот, если элементы больше <tex>x</tex>.#Если <tex>i</tex> <tex>=</tex> <tex>k</tex>, то возвращается значение <tex>x</tex>. Иначе вызывается запускается рекурсивно шаг 1, и выполняется поиск элемента в одной из частей массива: <tex>k</tex>-го в порядке возрастания элемента ой статистики в левой части массива,если при <tex>i</tex> <tex><k</tex> или <tex>(k- i - 1)</tex>, или -ой статистики в правой части, если при <tex>i</tex> <tex>></tex> <tex>k</tex>. ===ПсевдокодПример работы алгоритма === select(A, l, r, k) { if (r - l + 1 Рассмотрим работу алгоритма на массиве из <tex> 25 <= 5) { sort(A[l..r]); return A[k]; } for i = l:5:(r - 4) sort(A[i..i + 4]; //сортируем каждую группу len = r - l + 1; Medians[1..n/5] = A[(l + 2):5:(r - 2)]; x = select(Medians, 1, n/5, n/10); //x - рассекающий элемент A = share(A, l, r, x); //делим массив относительно элемента x for i = l to r if (A[i] == x) m = i; //находим индекс элемента x в массиве if (m = k) return A[m]; if (m tex> k) select(Aэлементов, k, r, m - k + 1); else select(A, l, k, m); }обозначенных кружками.

Отсортируем элементы каждой группы и выберем медианы. Вызовемся рекурсивно от медианПолученные медианы групп отмечены белыми кружками.

[[Файл:BFPRT2поиск.png| 300px]]

[[Файл:BFPRTРекурсивно вызовемся от медиан групп и получим рассекающий элемент. На рисунке он обозначен белым кружком, внутри которого изображен символ <tex> x </tex>.png| 80px]]

# времени работы для поиска медианы медиан, то есть <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 10Cn</tex> Так как <tex>T(n) \le leqslant 10Cn </tex>, то время работы алгоритма <tex>O(n)</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]