3.6. ПОРЯДКОВЫЕ СТАТИСТИКИ

С упорядочением тесно связана задача нахождения наименьшего элемента в -элементной последовательности Одно из очевидных решений состоит в следующем: упорядочить эту последовательность в порядке неубывания ее элементов и взять элемент. Как мы уже видели, это потребует сравнений. Аккуратно применяя стратегию "разделяй и властвуй", можно найти наименьший элемент за шагов. Важный частный случай — в этом случае середина последовательности отыскивается за линейное время.

Алгоритм 3.6. Нахождение k-го наименьшего элемента

Вход. Последовательность из элементов, принадлежащих линейно упорядоченному множеству, и целое число

Выход, наименьший элемент последовательности

Метод. Применяется рекурсивная процедура ВЫБОР, приведенная на рис. 3.10.

Проанализируем алгоритм 3.6 на интуитивном уровне, чтобы увидеть, почему он работает, как надо. Основная идея — данная последовательность разбивается по некоторому элементу на такие три подпоследовательности что содержит все элементы, меньшие все элементы, равные все элементы, большие Сосчитав число элементов в можно узнать, в каком из множеств лежит наименьший элемент. Таким приемом можно свести данную задачу к меньшей.

Чтобы получить линейный алгоритм, надо уметь за линейное время находить разбивающий элемент так, чтобы длина каждой из подпоследовательностей была бы не больше фиксированной доли длины последовательности Вся хитрость в способе выбора разбивающего элемента Последовательность разбивается на подпоследовательности по пять элементов в каждой. Каждая подпоследовательность упорядочивается, и из медиан всех этих подпоследовательностей составляется последовательность Теперь содержит только элементов, и можно найти ее медиану в пять раз быстрее, чем у последовательности из элементов.

Далее, не меньше четверти всех элементов последовательности 5 не превосходят и не меньше четверти ее элементов больше или равны Это проиллюстрировано на рис. 3.11. Возникает вопрос: причем здесь "магическое число" 5? Ответ заключается в том, что процедура ВЫБОР рекурсивно вызывается два раза, каждый раз

Рис. 3.10. (см. скан) Алгоритм выбора наименьшего элемента.

на последовательности, длина которой равна некоторой части длины последовательности Чтобы алгоритм работал линейное время, сумма длин этих двух последовательностей должна быть меньше Числа, отличные от 5, также годятся, но для некоторых из них процесс упорядочения подпоследовательностей будет дольше. В качестве упражнения предлагаем выяснить, какие же числа можно использовать вместо 5.

Теорема 3.9. Алгоритм 3.6 находит наименьший элемент в n-элементной последовательности за время

Доказательство. Корректность алгоритма доказывается непосредственно индукцией по и эту часть доказательства мы оставляем в качестве упражнения. Пусть время,

Рис. 3.11. Разбиение по алгоритму 3.6.

затрачиваемое на выбор наименьшего элемента из последовательности длины Длина последовательности составленной из медиан подпоследовательностей, не больше и потому рекурсивный вызов процедуры занимает время, не большее

Каждая из последовательностей имеет длину не более Чтобы увидеть это, заметим, что не менее элементов последовательности больше или равны и для каждого из них найдутся в два различных элемента, которые так же соотносятся с Следовательно, т. е. при длина последовательности меньше Аналогичное рассуждение применимо и к Поэтому рекурсивный вызов в строке 10 или 12 занимает времени не более Все остальные операторы тратят не более времени. Таким образом, для некоторой постоянной с

Из (3.8) по индукции можно доказать, что