Изменения

Перейти к: навигация, поиск
Нет описания правки
'''Алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна''' (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>\frac{3n}{10}</tex>, где <tex>n</tex> количество элементов в массиве, благодаря этому алгоритм работает за линейной время в любом случае.
== Описание алгоритма ==
#Все <tex>n</tex> элементов входного массива разбиваются на группы по пять элементов, в последней группе будет <tex>n</tex> <tex> mod</tex> <tex> 5</tex> элементов. Эта группа может оказаться пустой при <tex>n</tex> кратных <tex>5</tex>.
== Анализ времени работы алгоритма ==
Чтобы проанализировать время работы алгоритма, сначала определим нижнюю границу для количества элементов, превышающих по величине рассекающий элемент <tex>x</tex>. В общем случае как минимум половина медиан, найденных на втором шаге, больше или равны медианы медиан <tex>x</tex>. Таким образом, как минимум <tex>n</tex> <tex>/</tex> <tex>10</tex> групп содержат по <tex>3</tex> превышающих величину <tex>x</tex>, за исключение группы, в которой меньше <tex>5</tex> элементов и ещё одной группы, содержащей сам элемент <tex>x</tex>. Таким образом получаем, что количество элементов меньших больших элемента <tex>x</tex>, не менее <tex>\frac{3n}{10}</tex>, где <tex>n</tex> это количество элементов в массиве.
Проведя аналогичные рассуждения для элементов, которые меньше по величине, чем рассекающий элемент <tex>x</tex>, мы получим, что как минимум <tex>\frac{3n}{10}</tex> меньше, чем элемент <tex>x</tex>. Теперь проведем анализ времени работы алгоритма.
55
правок

Навигация