Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 43
Текст из файла (страница 43)
В новой версии процедуры разбиения непосредственно перед разбиением достаточно реализовать обмен. КАХООМПЕО-РАКТ1Т101ч (А, р, т) 1 ( = КАХООМ(р, т) 2 Обменять А[т[ и А[1] 3 гетогв РАкт1т1О1ч(А, р, т) В новой процедуре быстрой сортировки вместо процедуры РАкт1т1он вызывает- ся процедура КАнпом1ееО-РАкт1тюн.
Части!!. Сортировка и лорядковая статистика 208 Клыоом1еео421|1скзокт(А, р, г) 1 11р(г 2 С = КЛ|йРОМ1ЕЕО-РЛКТ1Т10Х(А, р, г) 3 Клс|оом1оео-11111скзокт(А, Р, 0 — 1) 4 КЛЫООМ1ХЕО-1 1111СКЗОКТ(А, О+ 1, г) Мы проанализируем этот алгоритм в следующем разделе. Упражнения 7.3.1 Почему мы анализируем ожидаемое время работы рандомизированного алгорит- ма, а не его время работы в наихудшем случае? 7.3.2 Сколько раз в ходе выполнения процедуры Клыоом1еео-Яо1скзокт в наихуд- шем случае вызывается генератор случайных чисел Кл|ч|зом? В наилучшем слу- чае? Выразите свой ответ через 1В-обозначения. 7.4.
Анализ быстрой сортировки 7.4.1. Анализ наихудшего случая В разделе 7.2 было показано, что при самом неудачном разбиении на каждом уровне рекурсии время работы алгоритма быстрой сортировки равно 9(пз). Интуитивно понятно, что зто наихудшее время работы рассматриваемого алгоритма. Докажем это утверждение.
С помощью метода подстановки (см. раздел 4.3) можно показать, что время работы алгоритма быстрой сортировки равно 0(пз). Пусть Т(п) — наихудшее время обработки процедурой Я111скзокт входных данных размером п. Тогда мы получаем следующее рекуррентное соотношение: Т(п) = шах (Т(д) + Т(и — о — 1)) + 9(п), 0<а(о-1 (7.1) В разделе 7.2 были приведены некоторые интуитивные рассуждения по поводу поведения алгоритма быстрой сортировки в наихудшем случае и обосновывалось, почему следует ожидать достаточно высокой производительности его работы. В данном разделе проведен более строгий анализ поведения этого алгоритма. Начнем этот анализ с наихудшего случая.
Подобный анализ применим как к процедуре 1~1|1скзокт, так и к процедуре Кл|чоом1ею-1 1111скзокт. Завершается раздел анализом ожидаемого времени работы процедуры Клы|зом!ееоЯпскзокт. 209 Гяава 7. Быстрая сортировка где параметр д изменяется в интервале от О до и — 1, поскольку на выходе процедуры Рлкт!т!он мы получаем две подзадачи, общий размер которых равен п — 1. Мы предполагаем, что Т(п) < спз для некоторой константы с. Подставив это неравенство в рекуррентное соотношение (7.1), получим Т(п) < шах (сиз + с(п — о — 1)з) + еэ(и) о<9< -! = с шах (д + (и — с — 1) ) + вэ(п) .
о«ч< -! Выражение дз + (и — д — 1) з достигает максимума на обоих юнцах интервала О < д < п — 1, что подтверждается тем, что вторая производная от него по д положительна (см. упр. 7.4.3). Это наблюдение позволяет нам сделать оценку шаха<9< -г(д~ + (п — с — 1)з) < (и — 1)з = пз — 2п + 1. Продолжая работу с границей для Т(п), получаем Т(п) < сиз — с(2п — 1) + !В(п) 2 поскольку константу с можно выбрать настолько большой, чтобы слагаемое с(2и — 1) доминировало над слагаемым ев(п). Таким образом, Т(п) = 0(пз). В разделе 7.2 мы встречались с частным случаем быстрой сортировки, при котором требовалось время П(пз), — это случай несбалансированного разбиения.
В упр. 7.4.1 нужно показать, что рекуррентное соотношение (7.1) имеет решение Т(п) = П(пз). Таким образом, время работы алгоритма быстрой сортировки (в наихудшем случае) равно вэ(п ). 7.4.2. Ожидаемое время работы Мы уже приводили интуитивный аргумент в пользу того, что ожидаемое время работы процедуры Клипом!хкп-Яо!сквокт равно 0(п!яп): если на каждом уровне рекурсии в разделении, производимом процедурой Клипом!око Рлкт!т!ом, в одну часть массива помещается произвольная фиксированная доля элементов, то высота дерева рекурсии равна !В(1я и), а время работы каждого его уровня — О(п). Даже после добавления некоторого количества новых уровней с наименее сбалансированным разбиением время работы останется равным 0(п !кп). Можно провести точный анализ математического ожидания времени работы процедуры Клноом!кно-Яо!скзокт. Для этого сначала нужно понять, как работает процедура разбиения, а затем получить для математического ожидания времени работы оценку 0(п 1я и).
Эта верхняя граница математического ожидания времени работы в сочетании с полученной в разделе 7.2 оценкой для наилучшего случая, равной 0(и!ли), позволяют сделать вывод о том, что математическое ожидание времени работы равно О(п!яп). Мы предполагаем, что значения всех сортируемых элементов различны.
Часть !!. Сортировка и аорядковак статистика 270 Время работы и сравнения Процедуры Олскзокт и Клн(эом(аппп-Ошскзокт отличаются только выбором опорного элемента; во всех прочих аспектах они идентичны. Таким образом, анализ процедуры Клнпом(хпп-Я(лскзокт можно провести, рассматривая процедуры (.Н!юкзодт и РАкт(т(о!ч, но в предположении, что опорные элементы выбираются из передаваемого процедуре Кл!чпоы(реп-Рлкт(тю(ч подмассива случайным образом. Время работы процедуры О(!юкзокт определяется преимущественно временем работы, затраченным на выполнение процедуры Рлкт(тю!ч. При каждом выполнении последней происходит выбор опорного элемента, который впоследствии не принимает участия ни в одном рекурсивном вызове процедур Я(!юкзокт и Рлкт(т(о(ч.
Таким образом, на протяжении всего времени выполнения алгоритма быстрой сортировки процедура Рлкт(тюг( вызывается не более п раз. Один вызов процедуры Рлкт(тюн выполняется в течение времени 0(1), к которому нужно прибавить время, пропорциональное количеству итераций цикла (ог в строках 3-6. В каждой итерации цикла аког в строке 4 опорный элемент сравнивается с другими элементами массива А. Поэтому, если известно общее количество выполнений строки 4, можно оценить полное время, которое затрачивается на выполнение цикла Тог в процессе работы процедуры Я(!юкзолт.
Лемма 7Л Пусть Х является количеством сравнений, выполняемых в строке 4 процедуры Рлкт(тюг( за время работы процедуры О(!юкзокт над и-элементным массивом. Тогда время работы процедуры Яыскзокт составляет 0(п + Х). Доказательство, Как следует из приведенных выше рассуждений, процедура Рлкт(тюг( вызывается не более и раз, выполняя при этом фиксированный объем работы и некоторое количество итераций цикла аког. Каждая итерация цикла Тог выполняет строку 4. Таким образом, наша цель заключается в том, чтобы вычислить величину Х, т.е.
полное количество сравнений, выполняемых при всех вызовах процедуры Рлкт(тюг(. Не будем пытаться проанализировать, сколько сравнений производится при каэ!сдам вызове этой процедуры. Вместо этого получим общую оценку полного количества сравнений. Для этого необходимо понять, в каких случаях в алгоритме производится сравнение двух элементов массива, а в каких— нет. Для упрощения анализа переименуем элементы массива А как гы гз,..., з„, где г, — г-й наименьший по порядку элемент.
Кроме того, определим множество с !! = (г„з;~ы..., г ), которое содержит элементы, расположенные между элементами г! и г включительно. Когда в алгоритме выполняется сравнение элементов гл и гу? Прежде чем ответить на этот вопрос, заметим, что сравнение каждой пары элементов производится не более одного раза. Почему? Дело в том, что элементы сравниваются с опорным элементом, который никогда не используется в двух разных вызовах процедуры Рлкт(тюы. Таким образом, после некоторого вызова этой процедуры Гласа 7. Быстраа сартирсила используемый в качестве опорного элемент впоследствии не будет сравниваться с другими элементами. Воспользуемся в нашем анализе индикаторными случайными величинами (см. раздел 5.2). Определим величину Хц — — 1(г, сравнивается с л 1, с помощью которой учитывается, произошло ли сравнение в течение работы алгоритма (но не в течение определенной итерации или определенного вызова процедуры Рлкт17101ч).
Поскольку каждая пара элементов сравнивается не более одного раза, полное количество сравнений, выполняемых на протяжении работы алгоритма, легко выразить следующим образом: с=1 1=1+1 Применяя к обеим частям этого выражения операцию вычисления математиче- ского ожидания и используя свойство ее линейности и лемму 5.1, получим и — 1 и Е[Х]=Е ~ ~~1 Х, в=1 1=1Ь1 = ~т ~ Е[Х1 ] 1=1 у=иы1 и — 1 и Рг (л! сравнивается с з;) (7.2) 1=1 !=~+1 Осталось вычислить величину Рг(гз сравнивается с л!). Предполагается, что опорные элементы выбираются случайным образом и независимо один от дру- ГОГО. Полезно поразмышлять о том, когда два элемента не сравниваются. Рассмотрим в качестве входных данных для алгоритма быстрой сортировки множество, состоящее из целых чисел от 1 до 10 (в произвольном порядке), и предположим, что в качестве первого опорного элемента выбрано число 7.
Тогда в результате первого вызова процедуры Рлкт17101ч все числа разбиваются на два множества: (1,2,3,4,5,6! и (8,9,10!. При этом элемент 7 сравнивается со всеми остальными. Очевидно, что ни одно из чисел, попавшее в первое подмножество (например, 2), больше не будет сравниваться ни с одним элементом второго подмножества (например, с 9).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
