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