Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 40
Текст из файла (страница 40)
(Это будет доказано в разделе 7.4.1.) Предположим, что такое несбалансированное разбиение возникает при каждом рекурсивном вызове. Для выполнения разбиения требуется время О (и). Поскольку рекурсивный вызов процедуры разбиения, на вход которой подается массив размера О, приводит к возврату из этой процедуры без выполнения каких-либо операций, Т (0) = О (1). Итак, рекуррентное соотношение, описывающее время работы этой процедуры, записывается следующим образом: Т(п) = Т (и — 1) + Т(0) + О(п) = Т(п — 1) + 6(п).
Интуитивно понятно, что при суммировании промежутков времени, затрачиваемых на каждый уровень рекурсии, получается арифметическая прогрессия (уравнение (А.2)), что дает нам в результате 6 (пз). В самом деле, с помощью метода Часть й. Сортировка и порядковая статистика 204 подстановок легко доказать, что Т (и) = О (пз) является решением рекуррентного соотношения Т (и) = Т (и — 1) + О (и) (см. упражнение 7.2-1). Таким образом, если на кахсцом уровне рекурсии алгоритма разбиение максимально несбалансированное, то время работы алгоритма равно 9 (пз). Следовательно, производительность быстрой сортировки в наихудшем случае не превышает производительности сортировки вставкой.
Более того, за такое же время алгоритм быстрой сортировки обрабатывает массив, который уже полностью отсортирован, — часто встречающаяся ситуация, в которой время работы алгоритма сортировки вставкой равно О (и). Наилучшее разбиение В самом благоприятном случае процедура РАкт1т|ом делит задачу размером п на две подзадачи, размер каждой из которых не превышает п/2, поскольку размер одной из них равен 1п/2), а второй — (и/21 — 1. В такой ситуации быстрая сортировка работает намного производительнее, и время ее работы описывается следующим рекуррентным соотношением: Т (п) < 2Т (и/2) + О (и) .
Это рекуррентное соотношение подпадает под случай 2 основной теоремы (теоремы 4.1), так что его решение — Т (и) = О (п1йп). Таким образом, разбиение на равные части приводит к асимптотически более быстрому алгоритму. Сбалансированное разбиение Как станет ясно из анализа, проведенного в разделе 7.4, в асимптотическом пределе поведение алгоритма быстрой сортировки в среднем случае намного ближе к его поведению в наилучшем случае, чем в наихудшем. Чтобы стало ясно, почему это так, нужно понять, как баланс разбиения отражается на рекуррентном соотношении, описывающем время работы алгоритма. Предположим, что разбиение происходит в соотношении один к девяти, что на первый взгляд весьма далеко от сбалансированности. В этом случае для времени работы алгоритма быстрой сортировки мы получим следующее рекуррентное соотношение: Т(п) < Т(9п/10) + Т(п/10) + сп, в которое явным образом входит константа с, скрытая в члене Й (и). На рис.
7.4 показано рекурсивное дерево, отвечающее этому рекуррентному соотношению. В узлах дерева приведены размеры соответствующих подзадач, а справа от каждого уровня — его время работы. Время работы уровней явным образом содержит константу с, скрытую в члене О (и). Обратите внимание, что время работы Глава 7. Быстрая сортировка 205 ял +л сл с л г 1оа, Лсл Дл 3» сл /~ /~ / 1 /~ /~ 1ля, ,ц;л лллл -----------М- сл /~ /~л ', --------Э <сл 1 .
— — — - -> < сл О(л 1ял1 Рис. 7.4. Рекурсивнос дерево, соответствующее делению задачи про- цедурой РАкт1тюн в соотношении 1:9 каждого уровня этого дерева равна сп. Так происходит до тех пор, пока не будет достигнута глубина !ок1о п = О (1йп). Время работы более глубоких уровней не превышает величину сп. Рекурсия прекращается на глубине 1ол ю/э п = = О (1й и); таким образом, полное время работы алгоритма быстрой сортировки равно О (п!к п).
Итак, если на каждом уровне рекурсии разбиение производится в соотношении один к девяти, время работы алгоритма быстрой сортировки равно 0 (п!кп). Другими словами, несмотря на то, что такое разбиение выглядит довольно несбалансированным, в асимптотическом пределе алгоритм ведет себя так же, как и при делении задачи на две одинаковые подзадачи. Фактически, даже разбиение в соотношении девяносто девять к одному приводит к тому, что время выполнения этого алгоритма будет равно 0 (тс1йп). Причина в том, что любое разбиение, характеризующееся конечной константой пропорциональности, приводит к образованию рекурсивного дерева высотой О (1йп) и временем работы каждого уровня 0 (и).
Таким образом, при любой постоянной величине пропорции полное время выполнения составляет 0 (и 1к и). Интуитивные рассуждения для среднего случая Чтобы получить представление о работе алгоритма быстрой сортировки в среднем случае, необходимо сделать предположение о том, как часто ожидается появление тех или иных входных данных. Поведение рассматриваемого алгоритма определяется относительным расположением элементов данного входного массива, 206 Часть П.
Сортировка и порядковая статистика а не их конкретной величиной. Как и при вероятностном анализе задачи о найме сотрудника, проведенном в разделе 5.2, пока что предположим, что все перестановки входных чисел равновероятны. Если алгоритм быстрой сортировки обрабатывает случайным образом выбранный входной массив, то маловероятно, чтобы разбиение на каждом уровне происходило в одном и том же соотношении, как это было в ходе проведенного выше неформального анализа. Предположим, что некоторые разбиения сбалансированы довольно хорошо, в то время как другие сбалансированы плохо.
Например, в упражнении 7.2-6 нужно показать, что соотношение размеров подзадач на выходе процедуры РАкт~ткхч примерно в 80',4 случаев сбалансировано лучше, чем девять к одному, а примерно в 20'А случаев — хуже. В среднем случае процедура РАкт~тюм производит и "хорошие" и "плохие" деления.
В рекурсивном дереве, соответствующем среднему случаю, хорошие и плохие разбиения равномерно распределены по всему дереву. Для упрощения интуитивных рассуждений предположим, что уровни дерева с плохими и хорошими разбиениями чередуются, и что хорошие разбиения получаются такими, как в наилучшем случае, а плохие — такими, как в наихудшем. На рис. 7.5а показаны разбиения на двух соседних уровнях такого рекурсивного дерева. В корне дерева время разбиения пропорционально и, а размеры полученных подмассивов равны и — 1 и О, что соответствует наихудшему случаю. На следующем уровне подмассив размера п — 1 делится оптимальным образом на подмассивы размеров (и — 1)/2 — 1 и (п — 1)/2.
Предположим, что для подмассива размером 0 время работы равно 1. Чередование таких хороших и плохих разбиений приводит к образованию трех подмассивов с размерами О, (и — 1)/2 — 1 и (и — 1)/2. При этом суммарное время разбиения равно О (и) + О (и — 1) = О (и).
Эта ситуация определенно не хуже показанной на рис. 7.5б, где изображен один уровень разбиения, в результате которого в течение времени О (и) образуются два подмассива с размерами (и — 1)/2. Однако в этом случае разбиение получается сбалансированным! Интуитивно понятно, что время О (и — 1), которое требуется на плохое разбиение, поглощается временем 6 (и), которое требуется на хорошее разбиение, а полученное в результате разбиение оказывается хорошим. Таким образом, время работы алгоритма быстрой сортировки, при которой на последовательных уровнях чередуются плохие и хорошие разбиения, ведет себя подобно времени работы алгоритма быстрой сортировки, при которой выполняются только хорошие разбиения. Оно также равно О (п 18п), просто константа, скрытая в О-обозначении, в этом случае несколько больше.
Строгий анализ рандомизированной версии алгоритма быстрой сортировки в среднем случае содержится в разделе 7.4.2. Глава 7. Быстрая сортировка 207 --3 н«»', ».ч «»-иц - ««»-!«н( «»-«лз «».и)«з а) Рнс. 7.5. а) Два уровня рекурсивного дерева быстрой сортировки. б) Хоро- шо сбалансированный уровень рекурсивного дерева. В обоих случаях время выполнения подзадач в заштрихованных эллипсах равно Й 1и) Упражнения 7.2-1.
С помощью метода подстановки докажите, что решение рекуррентного соотношения Т 1и) = Т «и — 1) + 01и) имеет вид Т «и) = О 1и~), как утверждалось в начале раздела 7.2. 7.2-2. Чему равно время работы процедуры О«««скзокт в случае, когда все элементы массива А одинаковы по величине? 7.2-3. Покажите, что если все элементы массива А различаются по величине и расположены в убывающем порядке, то время работы процедуры О«лскзокт равно О «,и'). 7.2-4. Сведения о банковских операциях часто записываются в хронологическом порядке, но многие предпочитают получать отчеты о состоянии своих банковских счетов в порядке нумерации чеков. Чеки чаще всего выписываются в порядке возрастания их номеров, а торговцы обычно обналичивают их с небольшой задержкой.
Таким образом, задача преобразования упорядочения по времени операций в упорядочение по номерам чеков — это задача сортировки почти упорядоченных массивов. Обоснуйте утверждение, что при решении этой задачи процедура 1ь«знктюы Вокт превзойдет по производительности процедуру О«лскзокт.
7.2-5. Предположим, что в ходе быстрой сортировки на каждом уровне происходит разбиение в пропорции 1 — сг к «з, где О < гг < 1/2 — константа. Покажите, что минимальная глубина, на которой расположен лист рекурсивного дерева, приблизительно равна — )яи!)ба, а максимальная глубина — приблизительно — 1к и/1б «1 — сг). (Округление до целых чисел во внимание не принимается.) * 7.2-6. Докажите, что для любой константы О < сг < 1/2 вероятность того, что процедура Рлкт«т«о«ч поделит случайно выбранный входной массив в более сбалансированной пропорции, чем 1 — гз к сг, приблизительно равна 1 — 2сг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
