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