Медианы и порядковые статистики

В этой главе мы рассматриваем такую задачу: дано множество из га чисел; найти тот его элемент, который будет г-м по счёту, если расположить элементы множества в порядке возрастания. В англоязычной литературе такой элемент называется г-ж порядковой статистикой (order statistic). Например, минимум (minimum) -это порядковая статистика номер 1, а максимум (maximum) - порядковая статистика номер га. Медианой (median) называется элемент множества, находящийся (по счёту) посередине между минимумом и максимумом. Точнее говоря, если га нечётно, то медиана - это порядковая статистика номер г = (га + 1)/2, а если га четно, то медиан даже две: с номерами г = га/2 и г = га/2 + 1. Можно ещё сказать, что, независимо от чётности га, медианы имеют номер г = [(га + l)/2j и г = [(га + 1)/2]. В дальнейшем мы будем называть медианой меньшую из двух (если их две).

Для удобства мы будем считать, что множество, в котором мы ищем порядковые статистики, состоит из различных элементов, хотя практически всё, что мы делаем, переносится на ситуацию, когда во множестве есть повторяющиеся элементы. Задача выбора элемента с данным номером (selection problem) состоит в следующем:

Дано: Множество А из га различных элементов и целое число г, 1 г га.

Найти: Элемент х £ А, для которого ровно г - 1 элементов множества А меньше х.

Эту задачу можно решить за время О (nig га): отсортировать числа, после чего взять г-ж элемент в полученном массиве. Есть, однако, и более быстрые алгоритмы.

В разделе 10.1 мы рассмотрим простейший случай: нахождение максимального и минимального элементов. Общая задача более интересна; ей посвящены два следующих раздела. В разделе 10.2 мы рассматриваем удобный на практике вероятностный алгоритм, который ищет порядковую статистику за время О (га) в среднем (имеется в виду математическое ожидание времени его работы на любом входе). В разделе 10.3 мы рассматриваем (представля-

ющий скорее теоретический интерес) детерминированный алгоритм, требующий времени О (га) в худшем случае.

10.1. Минимум и максимум

Сколько сравнений необходимо, чтобы во множестве из га чисел найти наименьшее? За га - 1 сравнений это сделать легко: надо последовательно перебирать все числа, храня значение наименьшего числа из уже просмотренных. Запишем этот алгоритм, считая, что числа заданы в виде массива А длины га.

Мшшим(А)

1min <- А[1]

2for г <т- 2 to length[A]

3do if min > A[i]

4then min <- A[i]

5return min

Разумеется, аналогичным образом можно найти и максимум.

Можно ли найти минимум еще быстрее? Нет, и вот почему. Рассмотрим алгоритм нахождения наименьшего числа как турнир среди га чисел, а каждое сравнение - как матч, в котором меньшее число побеждает. Чтобы победитель был найден, каждое из остальных чисел должно проиграть по крайней мере один матч, так что меньше га - 1 сравнений быть не может, и алгоритм Minimum оптимален по числу сравнений.

Интересный вопрос, связанный с этим алгоритмом - нахождение математического ожидания числа исполнений строки 4. В задаче 6-2 требуется показать, что эта величина есть O(lgra).

Одновременный поиск минимума и максимума

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

Если мы попросту найдем сначала минимум, а потом максимум, затратив на каждый из них по га - 1 сравнений, то всего будет 2га - 2 сравнения, что асимптотически оптимально. Можно, однако, решить эту задачу всего за 3[~га/2] - 2 сравнений. Именно, будем хранить значения максимума и минимума уже просмотренных чисел, а очередные числа будем обрабатывать по два таким образом: сначала сравним два очередных числа друг с другом, а затем

большее из них сравним с максимумом, а меньшее - с минимумом. При этом на обработку двух элементов мы затратим три сравнения вместо четырёх (кроме первой пары, где понадобится всего одно сравнение).

Упражнения

10.1-1 Покажите, что второе по величине число из га данных можно найти в худшем случае за га + [lgra] - 2 сравнения. (Указание. Ищите это число вместе с наименьшим.)

10.1-2* Покажите, что для одновременного нахождения наибольшего и наименьшего из га чисел в худшем случае необходимо не менее [Зга/2] - 2 сравнений. (Указание. В каждый момент элементы делятся на четыре группы: (1) непросмотренные (которые могут оказаться и минимальными, и максимальными); (2) те, что ещё могут оказаться минимальными, но заведомо не максимальны; (3) те, что ещё могут оказаться максимальными, но не минимальными; (4) отброшенные (которые заведомо не минимальны и не максимальны). Пусть а\, а2, а3, а± - количество элементов каждой группы. Как меняются эти числа при сравнениях?)

10.2. Выбор за линейное в среднем время

Хотя общая задача выбора выглядит более сложной, чем задача о минимуме или максимуме, её, как ни странно, тоже можно решить за время в (га). В этом разделе мы рассмотрим вероятностный алгоритм Randomized-Select для решения этой задачи, действующий по схеме «разделяй и властвуй». Он аналогичен алгоритму быстрой сортировки из главы 8: массив разбивается на меньшие части. Однако алгоритм быстрой сортировки, разбив массив на два куска, обрабатывает оба, а алгоритм Randomized-Select - только один из этих кусков. Поэтому он быстрее: среднее время быстрой сортировки есть О (га lgra), в то время как алгоритм Randomized-Select работает в среднем за время ©(га).

Алгоритм Randomized-Select использует процедуру Randomized-Partition, описанную в разделе 8.3, поведение которой (и, стало быть, всего алгоритма) зависит от датчика случайных чисел. Вызов Randomized-Select(A, р, г, г) возвращает г-ж по счёту в порядке возрастания элемент массива А\р. .г].