3.7. СРЕДНЕЕ ВРЕМЯ ДЛЯ ПОРЯДКОВЫХ СТАТИСТИК

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

но среднее время работы которого составляет лишь долю времени работы алгоритма 3.6.

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

Лемма 3.3. Если на пути выясняется, что является наименьшим элементом в то для любого либо либо

Доказательство. Допустим, что некоторый элемент не связан с отношением Покажем, что, поместив либо перед, либо после в линейном порядке, заданном на мы получим противоречие с предположением, что путь правильно установил, что является наименьшим элементом в Пусть входят остальные элементы из По предположению принадлежат

Если произвольный элемент в (соответственно в (соответственно то в силу транзитивности также принадлежит (соответственно Следовательно, можно построить такой линейный порядок совместимый с что все элементы множества предшествуют всем элементам из торые в свою очередь предшествуют всем элементам из

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

отношением то дерево не может правильно выбрать наименьший элемент из Случай исследуется аналогично.

Теорема 3.10. Если дерево решений, выбирающее наименьший элемент в множестве то глубина любого листа дерева не меньше

Доказательство. Рассмотрим путь в из корня к листу. По лемме 3.3 либо либо для каждого где элемент, выбранный в качестве наименьшего. Для элемента определим ключевое сравнение как первое сравнение на содержащее и такое, что выполнено одно из условий:

Интуитивно ключевое сравнение для это первое сравнение, из которого можно определить, предшествует элемент элементу или следует за ним.

Понятно, что всякий элемент кроме обладает ключевым сравнением; иначе не выполнилось бы ни ни Далее, легко видеть, что никакое сравнение не может быть ключевым для обоих сравниваемых элементов. Так как в ключевые сравнения должны вовлекаться элементов, то длина пути должна быть не меньше

Следствие. Нахождение наименьшего элемента в требует не меньше сравнений как в среднем, так и в худшем случае.

На самом деле для всех кроме можно доказать более сильный результат, чем теорема 3.10. (См. упр. 3.21-3.23.)

Если приходится искать алгоритм с хорошим средним временем, который вычисляет наименьший элемент в то подходит стратегия типа той, что применялась в алгоритме Быстрсорт.

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

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

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

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

Теорема 3.11. Среднее время работы алгоритма 3.7 линейно.

Рис. 3.12. Алгоритм выбора.

Доказательство. Пусть среднее время работы процедуры ВЫБОР на последовательности из элементов. Предположим для простоты, что все элементы множества различны. (При наличии повторяющихся элементов результат не изменится.)

Пусть элемента, выбранный в строке 2, является наименьшим элементом в Число может принимать значения равновероятно. Если то ВЫБОР вызывается для последовательности, состоящей из элементов, а если то для последовательности, состоящей из элементов. Поэтому среднее время работы рекурсии в строке 4 или 6 равно

Остальная часть процедуры ВЫБОР занимает время для некоторой постоянной с, так что при

В качестве упражнения на индукцию предлагаем доказать, что если то для всех

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Замечания по литературе

Книга Кнута [1973а] представляет собой энциклопедическое руководство по методам сортировки. Сортдеревом берет начало от Уильямса [1964]; некоторые улучшения сделаны Флойдом [1964]. Быстрсорт ввел Хоор [1962]. Улучшения Быстрсорт по схеме упр. 3.28 предложены Синглтоном [1969], а также Фрейзером, Мак-Келларом [1970]. Алгоритм 3.6 для нахождения порядковой статистики, линейный в худшем случае, изложен в работе Блюма, Флойда, Пратта, Ривеста, Тарьяна [1972]. Хейдиан, Соубел [1969] и Пратт, Яо [1973] исследуют число сравнений, необходимое для нахождения некоторых порядковых статистик.

Результат упр. 3.21 получен Кислицыным [1964]. Упр. 3.22, 3.23 и 3.29 взяты из работы Флойда, Ривеста [1973], где также приведена более сильная нижняя оценка, чем та, что указана в упр. 3.22. Упр. 3.19, 3.20 и некоторые обобщения обсуждаются в работах Гейла, Карпа [1970] и Лю [1972]. Интересное приложение сортировки к нахождению выпуклой оболочки множества точек на плоскости дано Грэхемом [1972]. Стабильная сортировка рассмотрена Хорватом [1974].