Алгоритмы - построение и анализ (1021735), страница 39
Текст из файла (страница 39)
Таким образом, если на кахсцом уровне рекурсии алгоритма разбиение максимально несбалансированное, то время работы алгоритма равно 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сг.
208 Часть П. Сортировка и порядковая статистика 7.3 Рандомизированная версия быстрой сортировки Исследуя поведение алгоритма быстрой сортировки в среднем случае, мы сделали предположение, что все перестановки входных чисел встречаются с равной вероятностью. Однако на практике это далеко не всегда так (см. упражнение 7.2-4). Иногда путем добавления в алгоритм этапа рандомизации (аналогично тому, как это было сделано в разделе 5.3) удается получить среднюю производительность во всех случаях.
Многие считают такую рандомизированную версию алгоритма быстрой сортировки оптимальным выбором для обработки достаточно больших массивов. В разделе 5.3 рандомизация алгоритма проводилась путем явной перестановки его входных элементов. В алгоритме быстрой сортировки можно было бы поступить точно так же, однако анализ упростится, если применить другой метод рандомизации, получивший название случайной выборки (гапдош яагпр!!пй). Вместо того чтобы в качестве опорного элемента всегда использовать А [г), такой элемент будет выбираться в массиве А [р..г) случайным образом.
Подобная модификация, при которой опорный элемент выбирается случайным образом среди элементов с индексами от р до г, обеспечивает равную вероятность оказаться опорным любому из г — р+ 1 элементов подмассива. Благодаря случайному выбору опорного элемента можно ожидать, что разбиение входного массива в среднем окажется довольно хорошо сбалансированным. Изменения, которые нужно внести в процедуры Рлкт1т1оы и ()о1скзокт, незначительны. В новой версии процедуры Рлкт1т1оы непосредственно перед разбиением достаточно реализовать перестановку: Клыоом12ю Рлкт1тюы(А, р, г) 1 г Клипом(р, г) 2 Обменять А[г) + А[и) 3 гетцгп Рлнт1тЮЫ(А, р, г) В новой процедуре быстрой сортировки вместо процедуры Рлкт1тюы вызывается процедура Клыоом12ю Рлкт1тюьп Клипом 12юЯяскзокт(А, р, г) 1 !1р(г 2 1)ЗЕП й КЛЫООМ1ХЮ РЛКт1тЮЫ(А, р, г) 3 Клыоом12юЯыскзокт(А, р, д — 1) 4 КЛНООМ12ЮЯГЛСКЗОКт(А, д+ 1, г) Этот алгоритм будет проанализирован в следующем разделе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
