Алгоритмы - построение и анализ (1021735), страница 47
Текст из файла (страница 47)
Медианы и порядковые статистики 241 которая исследуется в двух последующих разделах. В разделе 9.2 анализируется применяющийся на практике алгоритм, время работы которого в среднем составляет О (п) (предполагается, что все элементы различны). В разделе 9.3 приведен алгоритм, представляющий больший практический интерес, время работы которого достигает величины О (и) в наихудшем случае. 9.1 Минимум и максимум Сколько сравнений необходимо для того, чтобы найти минимальный элемент в и-элемеитном множестве? Для этой величины легко найти верхнюю границу, равную п — 1 сравнениям: мы по очереди проверяем каждый элемент множества и следим за тем, какой из них является минимальным на данный момент. В представленной ниже процедуре предполагается, что исследуется множество, состоящее из элементов массива А, где 1епутл [А] = п: мммим(А) 1 пнп ~ — А[Ц 2 аког г' — 2 1о 1епдй[А] 3 до и тгп ) А[т] 4 тпеп тгп - А[1] 5 гегнгп тгп Очевидно, что для поиска максимального элемента также понадобится не более п — 1 сравнений.
Является лн представленный выше алгоритм оптимальным? Да, поскольку можно доказать, что нижняя граница для задачи определения минимума также равна и — 1 сравнений. Любой алгоритм, предназначенный для определения минимального элемента множества, можно представить в виде турнира, в котором принимают участие все элементы. Каждое сравнение — зто поединок между двумя элементами, в котором побеждает элемент с меньшей величиной. Важное наблюдение заключается в том, что каждый элемент, кроме минимального, должен потерпеть поражение хотя бы в одном поединке. Таким образом, для определения минимума понадобится и — 1 сравнений, и алгоритм Мп п~мцм является оптимальным по отношению к количеству производимых в нем сравнений.
Одновременный поиск минимума и максимума В некоторых приложениях возникает необходимость найти как минимальный, так и максимальный элементы множества. Например, графической программе может понадобиться выполнить масштабирование множества координат (х, у) таким образом, чтобы они совпали по размеру с прямоугольной областью экрана или Часть И. Сортировка и порядковая статистика 242 другого устройства вывода. Для этого сначала надо определить максимальную и минимальную координаты. Несложно разработать алгоритм для поиска минимума и максимума в и-элементном множестве, производя при этом О (и) сравнений; при этом алгоритм будет асимптотически оптимальным. Достаточно просто выполнить независимый поиск минимального и максимального элементов.
Для выполнения каждой подзадачи понадобится и — 1 сравнений, что в сумме составит 2и — 2 сравнений. Однако на самом деле для одновременного определения минимума и максимума достаточно не более 3 (п/21 сравнений. Для этого необходимо следить за тем, какой из проверенных на данный момент элементов минимальный, а какой— максимальный. Вместо того, чтобы отдельно сравнивать каждый входной элемент с текущим минимумом и максимумом (для чего пришлось бы на каждый элемент израсходовать по два сравнения), мы будем обрабатывать пары элементов.
Образовав пару входных элементов, сначала сравним их один с другим, а затем меньший элемент пары будем сравнивать с текущим минимумом, а больший— с текущим максимумом. Таким образом, для каждой пары элементов понадобится по 3 сравнения. Способ начального выбора текущего минимума и максимума зависит от четности количества элементов в множестве и.
Если п нечетно, мы выбираем из множества один из элементов и считаем его значение одновременно и минимумом, н максимумом; остальные элементы обрабатываем парами. Если же и четно, то выбираем два первых элемента и путем сравнения определяем, значение какого из них будет минимумом, а какого — максимумом. Остальные элементы обрабатываем парами, как н в предыдущем случае.
Проанализируем, чему равно полное число сравнений. Если п нечетно, то нужно будет выполнить 3 (и/21 сравнений. Если же п четно, то выполняется одно начальное сравнение, а затем — еще 3 (и — 2)/2 сравнений, что в сумме дает Зи/2 — 2 сравнений. Таким образом, в обоих случаях полное количество сравнений не превышает 3 (п/21. Упражнения 9.1-1. Покажите, что для поиска второго в порядке возрастания элемента в наихудшем случае достаточно и + ~1~ п1 — 2 сравнений.
(Указание: найдите заодно и наименьший элемент.) 9.1-2. Покажите, что в наихудшем случае для поиска максимального и минимального среди и чисел необходимо выполнить ~Зп/21 — 2 сравнений. (Указание: рассмотрите вопрос о том, сколько чисел являются потенциальными кандидатами на роль максимума или минимума, и определите, как на это количество влияет каждое сравнение.) Глава 9. Медианы и порядковые статистики 243 9.2 Выбор в течение линейного ожидаемого времени Общая задача выбора оказывается более сложной, чем простая задача поиска минимума. Однако, как это ни странно, время решения обеих задач в асимптотическом пределе ведет себя одинаково — как О (п).
В данном разделе вниманию читателя представляется алгоритм типа "разделяй и властвуй" КлнпОм12еп Бе~.ест, предназначенный для решения задачи выбора. Этот алгоритм разработан по аналогии с алгоритмом быстрой сортировки, который рассматривался в главе 7.
Как и в алгоритме быстрой сортировки, в алгоритме Клнпом1геп Яа.ест используется идея рекурсивного разбиения входного массива. Однако в отличие от алгоритма быстрой сортировки, в котором рекурсивно обрабатываются обе части разбиения, алгоритм Кльпюмяеп Безвест работает лишь с одной частью. Это различие проявляется в результатах анализа обоих алгоритмов: если математическое ожидание времени работы алгоритма быстрой сортировки равно 9(п1бп), то ожидаемое время работы алгоритма Кльлэом1геп Бн.ест равно 9 (п), в предположении, что все элементы входных множеств различны. В алгоритме КЛИВОМ!ХЕО БЕЗВЕСТ используется процедура КЛМООМ12ЕО РЛК- тат~он, впервые представленная в разделе 7.3.
Таким образом, подобно процедуре Клнпом12еп ЯО1скзокт, Клнпом12еп Зесест — это рандомизированный алгоритм, поскольку его поведение частично определяется выводом генератора случайных чисел. Приведенный ниже код процедуры КлнпОм~хеп Яееест возвращает 1-й в порядке возрастания элемент массива А [р..т]: Кляюмию безвест(А, р, т,1) 1 11р=т 2 1йеп гегнгп А[р] 3 д < — КЛМООМЫЮ РЛКт1твн(А, р, т) 4 1~ †9 †5 й71=)с 1> Опорное значение — это ответ 6 Изеп ге1пгп АЦ 7 е1зе!1'1 < к 8 1йеп гегпгп кльпюмыеп Бн.ест(А, р, д — 1, г) 9 е1зе гегпгп клипом~ген Яееест(А, д + 1, т, г' — )с) После выполнения процедуры Клмпомыеп Рлкт~тюн, которая вызывается в строке 3 представленного выше алгоритма, массив А [р..т] оказывается разбитым на два (возможно, пустых) подмассива А [р..д — 1] и А [д+ 1..т].
При этом величина каждого элемента А [р..д — 1] не превышает А Ц, а величина каждого элемента А [д+ 1. т] больше А [9]. Как и в алгоритме быстрой сортировки, элемент А [д] будем называть опорным (рпо1). В строке 4 процедуры Клмзом- Часть П. Сортировка и порядковая статистика 244 1гео 8е ест вычисляется количество элементов 1с подмассива А [р..д], те. количество элементов, попадающих в нижнюю часть разбиения плюс один опорный элемент. Затем в строке 5 проверяется, является ли элемент А [д] 1-м в порядке возрастания элементом.
Если это так, то возвращается элемент А [д]. В противном случае в алгоритме определяется, в каком из двух подмассивов содержится с'-й в порядке возрастания элемент: в подмассиве А [р..д — 1] или в подмассиве А [д + 1. г]. Если 1 < )с, то нужный элемент находится в нижней части разбиения, и он рекурсивно выбирается из соответствующего подмассива в строке 8. Если же г ) Й, то нужный элемент находится в верхней части разбиения. Поскольку нам уже известны Й значений, которые меньше г-го в порядке возрастания элемента массива А [р..г] (это элементы подмассива А [р..д]), нужный элемент является (г — )с)-м в порядке возрастания элементом подмассива А [д+ 1. г], который рекурсивно находится в строке 9. Создается впечатление, что в представленном коде допускаются рекурсивные обращения к подмассивам, содержащим О элементов, но в упражнении 9.2-1 предлагается показать, что это невозможно.
Время работы алгоритма КАИООМ1хео Безвест в наихудшем случае равно 6 (из), причем даже для поиска минимума. дело в том, что фортуна может от нас отвернуться, и разбиение всегда будет производиться относительно наибольшего из оставшихся элементов, а само разбиение занимает время О (и).
Однако в среднем алгоритм работает хорошо, и поскольку он рандомизированный, никакие отдельно выбранные входные данные не могут гарантированно привести к наихудшему поведению алгоритма. Время, необходимое для выполнения алгоритма КАхоом1еео Безвест с входным массивом А [р..г], состоящим из и элементов, — это случайная величина. Обозначим ее как Т (и) и получим верхнюю границу Е [Т (и)] следующим образом.
Процедура КАноом1хео РАкт1т1оы с одинаковой вероятностью возвращает в качестве опорного любой элемент. Поэтому для каждого 1 < й < и в подмасснве А [р..д] с вероятностью 1/и содержится Й элементов (все они не превышают опорный элемент). Определим для lс = 1, 2,..., и индикаторную случайную величину Хзо где Хь = 1(В подмассиве А [р..д] содержится ровно х элементов) . В предположении, что все элементы различны, имеем: Е [Хь] = 1/и. (9.1) В момент вызова процедуры КА1ч1зом1хео Безвест и выбора опорного элемента А [д] заранее неизвестно, будет ли получен правильный ответ, после чего работа алгоритма сразу же прекратится, или произойдет рекурсивное обращение к подмассиву А [р..д — Ц или подмассиву А [д + 1..г]. Это будет зависеть от того, Глава 9. Медианы и порядковые статистики 245 Т(п) < ~~с Хь (Т(гпах(й — 1,п — й))+0(п)) = 1с= 1 и = ~> Хь Т(гпах(й — 1,п — й))+0(и).
я=1 Вычисляя математическое ожидание, получаем: Е[Т(п)] < < Е ~~1 Хь . Т (шах (й — 1, и — й)) + 0 (и) Я=1 и Е [Хсс Т (шах (й — 1, п — й))] + О (п) = я=1 Е[Хь] Е[Т(шах(й — 1,п — й))]+0(и) = Ь=1 1 — Е [Т (шах (й — 1, п — й))] + 0 (и) п я=1 (в силу линейности математического ожидания) (в соответствии с уравнением (В.23)) (в соответствии с уравнением (9.1)) Применяя уравнение (В.23), мы основывались на независимости случайных величин Хь и Т (гпах (й — 1, и — й)). В упражнении 9.2-2 предлагается доказать это предположение. Рассмотрим выражение шах (й — 1, и — й): (й — 1, если й ) (и/2], шах(й — 1,и — й) = '(п — й, если й < [п/2]. Если и четное, то каждое слагаемое от Т ( [п/2]) до Т (и — 1) появляется в сумме ровно дважды. Если же п нечетное, то дважды появляются все слагаемые, кроме где будет расположен искомый элемент относительно элемента А [о].
В предположении монотонного возрастания функции Т (и) необходимое для рекурсивного вызова процедуры КАнпом1гю Яньнст время можно ограничить сверху временем, необходимым для вызова этой процедуры с входным массивом максимально возможного размера. Другими словами, для получения верхней границы предполагается, что искомый элемент всегда попадает в ту часть разбиения, где больше элементов. При конкретном вызове процедуры КАмпом1хю Бн.нст индикаторная случайная величина Хь принимает значение 1 только для одного значения й, а при всех других й эта величина равна О. Если Хь = 1, то размеры двух подмассивов, к которым может произойти рекурсивное обращение, равны й — 1 и и — й. Таким образом, получаем следующее рекуррентное соотношение: Часть!1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
