Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 49
Текст из файла (страница 49)
Как и в алгоритме быстрой сортировки, в алгоритме Клнпом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. Сортировка и порядковая статистика 246 Т ((п/2) ), которое добавляется лишь один раз. Таким образом, имеем следующее соотношение: 2 п-1 Е )Т (и)) < — ~~1 Е )Т (lс)) + О (и) .
ь= (п/2) Найдем решение этого рекуррентного соотношения методом подстановок. Предположим, что Е )Т(п)] < си для некоторой константы с, удовлетворяющей начальным условиям рекуррентного соотношения. Кроме того, предположим, что для и, меньших какой-то константы, справедливо Т(и) = О (1)„эта константа будет найдена позже. Выберем также константу а, такую чтобы функция, соответствующая слагаемому О (и) (и описывающая нерекурсивную составляющую времени работы данного алгоритма), была ограничена сверху величиной ап для всех п > О. С помощью этой гипотезы индукции получаем: 2 ь — 1 Е)Т(и)) < — ~~1 сй+ ап = п ь= (а/2) 2с 1 12)-1 — Й вЂ” ~~1 Й +ап= п а=1 Ь=1 2с /(п — 1) п (1и/2) — 1) 1п/2~ п 1 2 2 2с /(п — 1) и (и/2 — 2) (и/2 — 1) 1 < ~ + ап = п 1 2 2 2с /пз — и пз/4 — Зп/2+ 2~ (+ап = п ~, 2 2 с1Зпз и = — ~ — + — — 2 +оп= п1,4 2 /Зп 1 21 =с1 — + — — — ~ +ап< 14 2 и) Зсп с 4 2 < — + — + ап = !сп с = си — ~ — — — — ап) .
~4 2 Чтобы завершить доказательство, нужно показать, что для достаточно больших и последнее выражение не превышает величину сп, или (что равносильно) что выполняется неравенство си/4 — с/2 — ап > О. Добавив к обеим частям этого неравенства с/2 и умножив их на и, получим неравенство п(с/4 — а) > с/2.
Если константа с выбрана таким образом, что с/4 — а > О, т.е. с > 4а, то обе части приведенного выше соотношения можно разделить на с/4 — а, что дает нам Глава 9. Медианы и порядковые статистики 247 следующий результат с/2 2с п> с/4 — а с — 4а Таким образом, если предположить, что для всех п < 2с/(с — 4а) справедливо Т (и) = О (1), то Е (Т (и)] = О (п). Итак, мы приходим к выводу, что для поиска порядковой статистики (в частности, медианы) требуется время, линейно зависящее от количества входных элементов (при этом предполагается, что все элементы различны по величине). Упражнения 9.2-1.
Покажите, что процедура Клмпом12но Зн.нст никогда не вызывается с массивом-параметром, содержащим нулевое количество элементов. 9.2-2. Докажите, что индикаторная случайная величина Хь и величина Т(шах()с — 1, и — Й)) независимы. 9.2-3.
Напишите итеративную версию процедуры Клноомын» Бн нст. 9.2-4. Предположим, что для выбора минимального элемента массива А = = (3, 2,9,0, 7, 5,4,8,6, 1) используется процедура Клипом!хю 8н.Ест. Опишите последовательность разделений, соответствующих наихудшей производительности этой процедуры. 9.3 Алгоритм выбора с линейным временем работы в наихудшем случае Рассмотрим алгоритм выбора, время работы которого в наихудшем случае равно О(п). Подобно алгоритму Клмоомыю Бн.нст, алгоритм Ян.нст находит нужный элемент путем рекурсивного разбиения входного массива.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
