Стр. 100 - Основы алгоритмов и структур данных

98 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
имени (k=n); отыскание второго наибольшего имени ( k = 2) эквивалентно
отысканию второго наименьшего (k = n – 1) и т. д.; поэтому можно считать, что
]
2
1[n k ≤ . Особый интерес представляет задача отыскания квантилей
1α0 ], α[ << = n k , и, в частности, медианы
2
1 α
= .
Конечно, все перечисленные варианты задачи выбора можно решить,
используя любой из методов полной сортировки имен, а затем тривиально
обращаясь к k – му наибольшему. Такой подход потребует порядка nlog( n)
сравнений имен независимо от значения k. Но при этом мы получаем гораздо
больше информации, чем требуется.
Поэтому нужен другой подход:
1-й путь. При использовании алгоритма сортировки наиболее подходящим
будет один из алгоритмов, основанных на выборе, т. е. либо простая сортировка
выбором, либо пирамидальная сортировка. В каждом случае мы можем
остановиться после того, как выполнены первые k шагов. Для простой
сортировки выбором это означает использование
2
)1 (
) ( ... )2 ( )1 ( +
− = − + + − + −kk kn k n
n n
сравнений имен, а для пирамидальной – использование (n+k log(n)) сравнений
имен. В обоих случаях мы получаем больше информации, чем нужно, потому
что мы полностью определяем порядок k наибольших имен. Это не страшно,
если k – константа, не зависящая от n, так как обрабатывается очень малое
количество дополнительной информации; но когда 2
1 α0 ], α[
≤< = n k , мы
сортируем таблицу длины n α и, таким образом, имеем дело с большим
объемом лишней информации.
2-й путь. Быстрая сортировка.
Она даёт разумный метод выбора k – го наибольшего имени из имён
x1,…,x n. Таблица разбивается на две подтаблицы: выше x1 и ниже x1, и затем
исследуется рекурсивно подходящая подтаблица.
Предположим, обнаружено, что x1 попадает в позицию j (то есть, что это
j – е наибольшее имя).
k = j, процедура закончена;
k < j – ищем k – е наибольшее среди x1,…,xj -1;
k > j – ищем (k – j) – е наибольшее среди xj+1,…,xn .