Алгоритмы - построение и анализ (1021735), страница 48
Текст из файла (страница 48)
Сортировка и порядковая статистика 246 Т ((п/2) ), которое добавляется лишь один раз. Таким образом, имеем следующее соотношение: 2 п-1 Е )Т (и)) < — ~~1 Е )Т (lс)) + О (и) . ь= (п/2) Найдем решение этого рекуррентного соотношения методом подстановок. Предположим, что Е )Т(п)] < си для некоторой константы с, удовлетворяющей начальным условиям рекуррентного соотношения. Кроме того, предположим, что для и, меньших какой-то константы, справедливо Т(и) = О (1)„эта константа будет найдена позже.
Выберем также константу а, такую чтобы функция, соответствующая слагаемому О (и) (и описывающая нерекурсивную составляющую времени работы данного алгоритма), была ограничена сверху величиной ап для всех п > О. С помощью этой гипотезы индукции получаем: 2 ь — 1 Е)Т(и)) < — ~~1 сй+ ап = п ь= (а/2) 2с — (и(2) -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 Алгоритм выбора с линейным временем работы в наихудшем случае Рассмотрим алгоритм выбора, время работы которого в наихудшем случае равно О(п). Подобно алгоритму Клмоомыю Бн.нст, алгоритм Ян.нст находит нужный элемент путем рекурсивного разбиения входного массива. Однако в основе этого алгоритма заложена идея, которая заключается в том, чтобы гарантировать хорошее разбиение массива. В алгоритме Бн вст используется детерминистическая процедура Рлкт~т~ом, которая применяется при быстрой сортировке (см.
раздел 7.1). Эта процедура модифицирована таким образом, чтобы одним из ее входных параметров был элемент, относительно которого производится разбиение. Для определения во входном массиве (содержащем более одного элемента) 1-го в порядке возрастания элемента, в алгоритме Яньнст выполняются следующие шаги (если п = 1, то процедура Ян.ест просто возвращает единственное входное значение.) 1. Все п элементов входного массива разбиваются на 1п/51' групп по 5 элементов в каждой и одну группу, содержащую оставшиеся п пзог1 5 элементов (впрочем, эта группа может оказаться пустой).
248 Часть й. Сортировка и порядковая статистика 2. Сначала по методу вставок сортируется каждая из ~п/51 групп (содержащих не более 5 элементов), а затем в каждом отсортированном списке, состоящем из элементов групп, выбирается медиана. 3.
Путем рекурсивного использования процедуры Бш.лет определяется медиана х множества из ~п/51 медиан, найденных на втором шаге. (Если этих медиан окажется четное количество, то, согласно принятому соглашению, переменной х будет присвоено значение нижней медианы.) 4. С помощью модифицированной версии процедуры Рдкт]т1ом входной массив делится относительно медианы медиан х. Пусть число )с на единицу превышает количество элементов, попавших в нижнюю часть разбиения. Тогда х — )с-й в порядке возрастания элемент, и в верхнюю часть разбиения попадает и — )с элементов. 5.
Если з = )с, то возвращается значение х. В противном случае процедура Бн бст вызывается рекурсивно, и с ее помощью выполняется поиск з-го в порядке возрастания элемента в нижней части, если з < )с, или в верхней части, если з > lс. Чтобы проанализировать время работы процедуры Бв.лст, сначала определим нижнюю границу для количества элементов, превышающих по величине опорный элемент х. Разобраться в этой бухгалтерии поможет рис. 9.1. На этом рисунке и элементов представлены в виде маленьких кружков, а каждая группа— отдельной колонкой. Медианы групп обозначены белыми кружками, а медиана медиан — белым кружком, рядом с которым стоит символ х.
(При определении медианы четного количества элементов используется нижняя медиана.) Стрелки проведены в направлении от больших элементов к меньшим. Из рисунка видно, что в каждой полной группе из 5 элементов, расположенной справа от х, содержится по 3 элемента, превышающих по величине х, а в каждой полной группе из 5 элементов, расположенной слева от х, содержится по 3 элемента, меньших по величине, чем х. Элементы, которые превышают х, выделены серым фоном. В общем случае как минимум половина медиан, найденных на втором шаге, больше или равны медианы медиан х'. Таким образом, как минимум ~п/51 групп содержат по 3 элемента, превышающих величину х, за исключением группы, в которой меньше пяти элементов (такая группа существует, если и не делится на 5 нацело), и еще одной группы, содержащей сам элемент х. Не учитывая эти две группы, приходим к выводу, что количество элементов, величина которых превышает х, удовлетворяет следующему неравенству: 3 (~- Н1 — 2) > — — 6.
'Согласно прсдположенню о том, что все чнсла различаются, каждая нз этих медиан больше нлн меньше х, за исключением самой медианы х. Часть П. Сортировка и порядковая статистика 250 часть рекуррентного соотношения, получим: Т (и) < с (и/5) + с (7п/10 + 6) + аи < < сп/5 + с + 7си/10 + бс + аи = = 9си/10 + 7с+ аи = = си + ( — сп/10 + 7с+ ап) . Это выражение не превышает величину сп, если выполняется неравенство -си/10+ 7с+ ап < О. (9.2) При п > 70 неравенство (9.2) эквивалентно неравенству с > 10а (и/(и — 70)). Поскольку мы предположили, что п > 140, то и/(и — 70) < 2, а значит, если выбрать с > 20а, то будет удовлетворяться неравенство (9.2). (Заметим, что в константе 140 нет ничего особенного; вместо нее можно было бы взять любое другое целое число, превышающее 70, после чего соответствующим образом нужно было бы выбрать константу с.) Таким образом, в наихудшем случае время работы алгоритма Бееест линейно зависит от количества входных элементов.
Как и в алгоритмах сортировки сравнением, которые рассматривались в разделе 8.1, в алгоритмах Белеет и КАмпом~геп Бееест информация о взаимном расположении элементов извлекается только путем их сравнения. Как было доказано в главе 8, в модели сравнений сортировка выполняется в течение времени П (и1кп), даже в среднем (см. задачу 8-1). В этой же главе был рассмотрен алгоритм сортировки, время работы которого линейно зависит от количества сортируемых элементов, но в нем делаются дополнительные предположения относительно входных данных.
Для работы представленных в настоящей главе алгоритмов выбора, время работы которых такое же, напротив, никаких дополнительных предположений не требуется. К этим алгоритмам не применима нижняя граница й (и 18п), поскольку задача выбора в них решается без сортировки. Таким образом, время работы рассмотренных выше алгоритмов линейно, поскольку в них не производится сортировка. Линейная зависимость от количества входных элементов не является результатом каких-то дополнительных предположений о входных данных, как в случае алгоритмов сортировки, описанных в главе 8. Для сортировки сравнением даже в среднем требуется время П (и 18 и), так что предложенный во введении к этой главе метод сортировки и индексирования асимптотически неэффективен.
Упражнения 9.3-1. В алгоритме Ян.ест все входные элементы делятся на группы по 5 элементов в каждой. Было бы время работы этого алгоритма линейным, если Глава 9. Медианы н порядковые статистики 251 бы входной массив делился на группы по 7 элементов в каждой? Дока- жите, что время работы алгоритма не будет линейным, если в каждой группе будет по 3 элемента.
9.3-2. Проанализируйте алгоритм Бпьпст и покажите, что при п > 140 как минимум (и/41 элементов превышают по величине медиану медиан х, и как минимум (и/41 элементов меньше х. 9.3-3. Покажите, каким образом можно выполнить быструю сортировку за время О (и 18 и) в наихудшем случае, считая, что все элементы различны. элементов 1-го в порядке возрастания элемента, применяется только опе- рация сравнения. Покажите, что с помощью этого алгоритма можно так- же найти 4 — 1 наименьших элементов и и — 1 наибольших элементов, не выполняя никаких дополнительных сравнений. 9.3-5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
