Минимизация числа сравнений в худшем случае в алгоритме поиска порядковых статистик

Аннотация

В работе предложена постановка задачи параметрической оптимизации алгоритма выбора М. Блума, Р. Флойда, В. Пратта, Р. Райвеста и Р. Тайрьяна с линейным временем работы в наихудшем случае. Определяется значение параметра, обеспечивающего минимальную теоретическую верхнюю границу числа сравнений в худшем случае для выполнения алгоритма. Исследуется полученная в результате численных экспериментов зависимость числа сравнений в алгоритме поиска порядковых статистик от различных значений параметра.