Randomized-Select(A,p, г, г)

1if р = г

2then return А\р]

3q <- Randomized-Partition(A,p, г)

4/г <- q - р + 1

5if г /г

6then return Randomized-Select(A,р, q, г)

7else return Randomized-Select(A, g + 1, г, г -/г)

После исполнения процедуры Randomized-Partition в строке 3 массив А\р .. г] состоит из двух непустых частей А\р .. q] и A[q + l..r], причём всякий элемент А[р..д] меньше всякого элемента А[д+1.. г]. В строке 4 вычисляется количество элементов в массиве А\р. .q]. Дальнейшее зависит от того, в каком из этих двух массивов лежит г-ж по величине элемент массива А\р. .г]. Если г к, то нужный нам элемент лежит в левой части (массиве А\р . .q]), откуда и извлекается в результате (рекурсивного) вызова Randomized-Select в строке 6. Если же i > к, то все к элементов левой части (А[р..д]) заведомо меньше искомого, который можно найти как [г - к)-ж по счёту элемент массива A[q + 1. .г] (строка 7).

Время работы алгоритма Randomized-Select (с учётом времени работы процедуры Randomized-Partition) в худшем случае есть 0(га2), даже если мы ищем всего лишь минимум: в самом деле, при особом невезении может оказаться, что мы все время разбиваем массив возле наибольшего оставшегося элемента. Однако случайный выбор гарантирует, что для любого входа среднее время работы алгоритма будет невелико.

Докажем это. Рассмотрим для каждой из возможных перестановок п элементов математическое ожидание времени работы алгоритма (среднее по всем случайным выборам). Пусть Т(п) - максимальное из этих ожиданий. Как мы отмечали в разделе 8.4, после вызова Randomized-Partition левая часть разбиения содержит 1 элемент с вероятностью 2/га, и содержит г > 1 элементов с вероятностью 1/га для любого г от 2 до га - 1. Можно считать, что Т(п) монотонно возрастает с ростом га (если это не так, заменим Т(п) на Г(га) = тах1гга Г(г) и повторим все рассуждения для Г). Заметим, что худшим случаем будет тот, когда г-ж по счёту элемент попадает в большую из двух половин, на которые разбивается мае-

Глава 10 Медианы и порядковые статистики сив. Отсюда имеем:

Т(га) - [r(max(l, га - 1)) + Т(тах(/г, га - к))\ + О

к=1

п-1

- Т(га-1) + 2Т(к) +0

га ,

к=\п/2] п-1

= - Е пк)+о(П)

к=\п/2]

(мы сгруппировали одинаковые слагаемые при переходе от первой строки ко второй и отбросили Т(п - 1)/га при переходе от второй строки к третьей, так как в худшем случае Т(п - 1) = О (га2), и тем самым слагаемое Г(га - 1)/га можно включить в О(га)).

Теперь докажем, что Т(п) era, рассуждая по индукции (как выбрать с, мы скажем после). В самом деле, пусть неравенство T(j) cj верно для всех j < га. Тогда, используя формулу для суммы арифметической прогрессии, получаем, что

2 п~Х

Т(п) <С -ск + 0(п)

к=\п/2]

2с га га/2 + 1 + га - 1

< - • - •--Ь С га

га 22V 7

Зсга

= - + О(га) era,

если выбрать с столь большим, чтобы с/4 превосходило константу, подразумеваемую в слагаемом О (га).

Стало быть, любая порядковая статистика, и медиана в том числе, может быть найдена за линейное в среднем время.

Упражнения

10.2-1 Напишите версию процедуры Randomized-Select, не использующую рекурсии.

10.2-2 Предположим, что мы используем алгоритм Randomized-Select для выбора наименьшего элемента из массива А = (3,2,9,0,7,5,4,8,6,1). Опишите последовательность разбиений, соответствующую худшему случаю.

10.2-3 Будет ли алгоритм Randomized-Select правильно работать, если в массиве А есть равные элементы (как мы помним, в этом случае процедура Randomized-Partition разбивает А\р. .г]

на части А\р .. q] и A[q + 1.. г] таким образом, что всякий элемент А\р .. q] не превосходит всякого элемента A[q + 1.. г])?

10.3. Выбор за линейное в худшем случае время

Теперь рассмотрим (детерминированный) алгоритм Select, решающий задачу о порядковых статистиках за время О (га) в худшем случае. Как и Randomized-Select, этот алгоритм основан на последовательном разбиении массива на меньшие части; в данном случае, однако, мы гарантируем, что выбранное разбиение не является неудачным. Алгоритм Select использует (детерминированную) процедуру Partition (см. описание алгоритма быстрой сортировки в разд. 8.1), модифицированную таким образом, чтобы элемент, с которым сравнивают, задавался как параметр.

Алгоритм Select находит г-ж по порядку элемент в массиве размера га > 1 следующим образом:

1.Разбить га элементов массива на [п/5\ групп по 5 элементов и (возможно) одну группу, в которой менее пяти элементов.

2.Найти медиану каждой из [~га/5] групп (для чего отсортировать группу вставками).

3.Вызвав (рекурсивно) процедуру Select, найти число ж, являющееся медианой найденных [~га/5] медиан.

4.Вызвав модифицированную процедуру Partition, разбить массив относительно найденной «медианы медиан». Пусть к - количество элементов в нижней части этого разбиения (в верхней части, стало быть, n - k).

5.Вызвав (рекурсивно) процедуру Select, найти г-ую порядковую статистику нижней части разбиения, если i . к, или (i - k)-ю порядковую статистику верхней части разбиения, если г > к.

Оценим время работы алгоритма Select. Для начала выясним, сколько чисел заведомо будут больше «медианы медиан» ж (см. рис. 10.1). Не менее половины медиан, найденных на втором шаге, будут больше или равны ж. Стало быть, по крайней мере половина из [~га/5] групп даст по три числа, больших ж, за двумя возможными исключениями: группа, содержащая ж, и последняя неполная группа. Тем самым имеется не менее

Зга

>--6.

10

элементов, заведомо больших ж, и точно так же получаем, что имеется не менее Зга/10 - 6 элементов, заведомо меньших ж. Значит, алгоритм Select, рекурсивно вызываемый на пятом шаге, будет обрабатывать массив длиной не более 7га/10 + 6.