Изменения

Перейти к: навигация, поиск
Нет описания правки
{{Определение
|definition=
'''<tex>k</tex>-ой порядковой статистикой''' набора элементов линейно упорядоченного множества называется такой его элемент, который является <tex>k</tex>-ым элементом набора в порядке сортировки
}}
== Историческая справка ==
 
'''Алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна''' (BFPRT-алгоритм) создан Мануэлем Блюмом (Manuel Blum), Робертом Флойдом (Robert Floyd), Воганом Рональдом Праттом (Vaughan Ronald Pratt), Роном Ривестом (Ron Rivest) и Робертом Тарьяном (Robert Tarjan) в 1973 году.
==Идея алгоритма==
Этот алгоритм является модификацией алгоритма [[Поиск k-ой порядковой статистики|поиска k-ой порядковой статистики]]. Важное отличие заключается в том, что время работы алгоритма в наихудшем случае — <tex>O(n)</tex>, где <tex>n</tex> — количество элементов в множестве. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива. Алгоритм выбирает такой рассекающий элемент, что количество чисел, которые меньше рассекающего элемента, не менее <tex>\frac{3n}{10}</tex>. Элементов же больших опорного элемента, также не менее <tex>\frac{3n}{10}</tex>. Благодаря этому алгоритм работает за линейное время в любом случае.
Анонимный участник

Навигация