55
правок
Изменения
Нет описания правки
'''Алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна''' (BFPRT-алгоритм) создан Мануэлем Блюмом (Manuel Blum), Робертом Флойдом (Robert Floyd), Воганом Рональдом Праттом (Vaughan Ronald Pratt), Роном Ривестом (Ron Rivest) и Робертом Тарьяном (Robert Tarjan) в 1973 году.
==Особенность Идея алгоритма==Этот алгоритм почти ни чем не отличается от алгоритма [[Поиск k-ой порядковой статистики|поиска k-ой порядковой статистики]], но имеет важное отличие в том, что время работы алгоритма в наихудшем случае равно <tex>O(n)</tex> (это , что будет доказано ниже). Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива. Алгоритм выбирает такой рассекающий элемент, что количество чисел, которые меньше рассекающего элемента, не менее <tex>\frac{3n}{10}</tex>, где <tex>n</tex> количество элементов в массиве, благодаря этому алгоритм работает за линейной время в любом случае.
== Описание алгоритма ==
#Все <tex>n</tex> элементов входного массива разбиваются на группы по пять элементов, в последней группе будет <tex>n</tex> <tex> mod</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><</tex> <tex>k</tex>, или в правой части, если <tex>i</tex> <tex>></tex> <tex>k</tex>.
===Псевдокод===
for (i = 1 to n/5) do
x[i] = select(S[i],3) //найдем медианы S[i];
M = select({x[i]}, n/10) // M - — рассекающий элемент;
partition L into L1<M, L2=M, L3>M // разобьем L на подмножества L1, где все элементы меньше M;
if (k <= length(L1)) // L3, где все элементы больше M и L2 равное M;
== Анализ времени работы алгоритма ==
Пусть <tex>T(n)</tex> - — время работы алгоритма для <tex>n</tex> элементов, тогда оно не больше, чем сумма:
# времени работы на сортировку групп и разбиение по рассекающему элементу, то есть <tex>Cn</tex>;
# времени работы для поиска медианы медиан, то есть <tex>T(\frac{n}{5})</tex>;
# времени работы для поиска <tex>k</tex>-го элемента в одной из двух частей массива, то есть <tex>T(s)</tex>, где <tex>s</tex>- — количество элементов в этой части. Но <tex>s</tex> не превосходит <tex>\frac{7n}{10}</tex>, так как чисел, меньших рассекающего элемента, не менее <tex>\frac{3n}{10}</tex> - — это <tex>\frac{n}{10}</tex> медиан, меньших медианы медиан, плюс не менее <tex>\frac{2n}{10}</tex> элементов, меньших этих медиан. С другой стороны, чисел, больших рассекающего элемента, так же не менее <tex>\frac{3n}{10}</tex>, следовательно <tex> s \le \frac{7n}{10}</tex>, то есть в худшем случае <tex> s = \frac{7n}{10}</tex>.
Тогда получаем, что
