Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 42
Текст из файла (страница 42)
В соответствии со случаем 2 основной теоремы (теорема 4.1) это рекуррентное соотношение имеет решение Т(и) = 6(п 1к п). При сбалансированности двух частей разбиения на каждом уровне рекурсии мы получаем асимптотически более быстрый алгоритм. Часть Рй Сортировка и порядковая статистика Сбалансированное разбиение Как станет ясно из анализа, проведенного в разделе 7.4, в асимптотическом пределе поведение алгоритма быстрой сортировки в среднем случае намного ближе к его поведению в наилучшем случае, чем к поведению в наихудшем случае. Чтобы стало ясно, почему это так, нужно понять, как баланс разбиения отражается на рекуррентном соотношении, описывающем время работы алгоритма.
Предположим, например, что разбиение всегда происходит в соотношении один к девяти, что, на первый взгляд, весьма далеко от сбалансированности. В этом случае для времени работы алгоритма быстрой сортировки мы получим рекуррентное соотношение Т(п) = Т(9п(10) + Т(п,110) + сп, в которое явным образом входит константа с, скрытая в члене ьВ(п). На рис.7.4 показано дерево рекурсии, отвечающее этому рекуррентному соотношению. Обратите внимание, что каждый уровень этого дерева имеет стоимость сп, и так до тех пор, пока не будет достигнуто граничное условие на глубине !о8ю и = св(!8 п); после этого стоимость более глубоких уровней не превышает величину сп.
Рекурсия прекращается на глубине 1обзо7а п = 9(18 п); таким образом, общая стоимость быстрой сортировки равна О!п18п), Итак, если на каждом уровне рекурсии разбиение производится в соотношении один к девяти (что интуитивно воспринимается как сильный дисбаланс), время работы алгоритма быстрой сортировки равно 0(п18п) — асимптотически такое же, как и при сбалансированном разбиении. Фактически любое разбиение, характеризующееся конечной константой пропорциональности, приводит к образованию дерева рекурсии высотой св(18 и) со стоимостью каждого уровня, равной 0(п).
Следовательно, при любой постоянной пропорции разбиения полное время работы быстрой сортировки составляет 0(п 18 п). Интуитивные рассуждения для среднего случая Чтобы получить ясное представление о рандомизированном поведении алгоритма быстрой сортировки, необходимо сделать предположение о том, как часто ожидается появление тех или иных входных данных. Поведение быстрой сортировки зависит от относительного расположения значений во входном массиве, а не от их конкретных величин.
Как и при вероятностном анализе задачи о найме в разделе 5.2, пока что предположим, что все перестановки входных чисел равновероятны. Если алгоритм быстрой сортировки работает со случайным образом выбранным входным массивом, то маловероятно, чтобы разбиение на каждом уровне происходило в одном и том же соотношении, как это было в ходе проведенного выше неформального анализа. Ожидается, что одни разбиения будут хорошо сбалансированы, в то время как другие окажутся сбалансированными плохо. Например, в упр. 7.2.6 нужно показать, что соотношение размеров подзадач на выходе процедуры РАкт!тюн примерно в 80% случаев сбалансировано лучше, чем девять к одному, и примерно в 20% случаев — хуже.
Глава Х оыстроя сортировка 705 1 !ли 9 тб и и сй 100 100 /з /з, / 1 1обз 9 п 81 !!и й в сй /~ /'з 1оя10 91 729 1000 1000 /~ /', --в < сй 1 "-"в' < сй О(и!би) Рис. 7.4. Дерево рекурсии для алгоритма Ошскзоит, в котором процедура Рлкт!тюн всегда выполняет разбиение в соотношении девять к одному, дающее время рабаты 0(и 1я и). Узлы показывают размеры подзадач; стоимости уровней показаны справа.
Стоимость уровня неявно включает константу с в члене О(и). В среднем случае процедура Рдкт1т(о!4 производит как "хорошие", так и "плохие" деления. В дереве рекурсии, соответствующем среднему случаю, хорошие и плохие разбиения равномерно распределены по всему дереву. Для упрощения интуитивных рассуждений предположим, что уровни дерева с плохими и хорошими разбиениями чередуются, и что хорошие разбиения получаются такими, как в наилучшем случае, а плохие — такими, как в наихудшем. На рис.7.5,(а) показаны разбиения на двух соседних уровнях такого дерева рекурсии. В юрие дерева стоимость разбиения равна п, а размеры полученных подмассивов равны п — 1 и О, что соответствует наихудшему случаю. На следующем уровне подмассив размером п — 1 делится оптимальным образом на подмассивы размерами (и — 1)/2 — 1 и (п — 1)/2.
Будем считать, что для подмассива размером О стоимость равна 1. Комбинация плохого и хорошего разбиений приводит к образованию трех подмассивов с размерами О, (п — 1)/2 — 1 и (п — 1)/2 и суммарной стоимостью В(п) + 9(п — 1) = тз(п). Эта ситуация, определенно, не хуже показанной на рис. 7.5, (б), на котором представлен один уровень разбиения со стоимостью Н(п), создающий два подмассива размерами (п — 1)/2. Однако в этом случае разбиение получается сбалансированным! Интуитивно понятно, что время 0(п — 1), которое требуется для плохого разбиения, поглощается временем тЭ(п), которое требуется для хорошего разбиения, а полученное в результате разбиение оказывается хорошим.
Таким образом, время работы алгоритма быстрой сортировки, при юторой иа последовательных уровнях чередуются плохие и хорошие разбиения, ведет себя так же, как время работы быстрой сортировки для одних лишь хороших разбиений. Оно также равно 0(п )я п), просто константа, скрытая в О-обозначении, Часть 11 Сортировка и оорядковав статистика 206 :,'ъ.:,.-- ------- - - ю 8(л) **- *-ч* 8(л) (б) (а) Рнс.
7.5. (а) Два уровня дерева рекурсии для быстрой сортировки. Стоимость разбиения в корне равна п и генерирует плохое разбиение, т.е. подмассивы размерами О и п — 1. Разбиение подмасснва размером п — 1 имеет стоимость и — 1 и генерирует хорошее разбиение — подмассивы размерами (и — 1)/2 — 1 и (и — 1)/2.
(б) Хорошо сбалансированный уровень дерева рекурсии. В обеих частях стоимость разбиения для задач в заштрихованнмх эллипсах составляет 9(п). Задачи, которые остается решить в случае (а), и показанные в заштрихованных прямоугольниках, оказываются не больше подзадач, которые следует решить в случае (б). в этом случае несколько больше. Строгий анализ ожидаемого времени работы рандомизированной версии быстрой сортировки содержится в разделе 7А.2. Упражнении 7.2.1 С помощью метода подстановки докажите, что решение рекуррентного соотношения Т(п) = Т(п — 1)+9(п) имеет вид Т(п) = тз(пз), как угверхщалось в начале раздела 7.2. 7.2.2 Чему равно время работы процедуры О()1СКЗОКт в случае, когда все элементы массива А одинаковы по величине? 7.2.3 Покажите, что если все элементы массива А различаются по величине и расположены в убывающем порядке, то время работы процедуры О()1СКЗОКт равно ~( 2) 7.2.4 Сведениа о банковских операциях часто записываются в хронологическом порядке, но многие предпочитают получать отчеты о состоянии своих банковских счетов в порядке нумерации чеков.
Чеки чаще всего выписываются в порядке возрастания их номеров, а торговцы обычно обналичивают нх с небольшой задержкой. Таким образом, задача преобразования упорядочения по времени операций в упорядочение по номерам чеков — это задача сортировки почти упорядоченных массивов. Обоснуйте утверждение, что при решении этой задачи процедура 1)чкдкт(о)ч-Бокт обычно превосходит по производительности процедуру ()(лскзОКТ.
гог Глава Х Быстрал сортировка 7.2.5 Предположим, что в ходе быстрой сортировки на каждом уровне происходит разбиение в пропорции 1 — о к ск, где О < сл < 1/2 — константа. Покажите, что минимальная глубина, на которой расположен лист дерева рекурсии, приблизительно равна — !ко/1я о, а максимальная глубина — приблизительно — 1я и/1к(1 — ск). (Об округлении до целочисленных значений можно не беспокоиться.) 7.2.6 * Докажите, что для любой константы О < си < 1/2 вероятность того, что процедура РАнт1тюн поделит случайно выбранный входной массив в более сбалансированной пропорции, чем 1 — ск к о, приблизительно равна 1 — 2св. 7.3.
Раидомизироваииая быстрая сортировка Исследуя поведение алгоритма быстрой сортировки в среднем случае, мы делали предположение, что все перестановки входных чисел встречаются с равной вероятностью. Однако на практике это далеко не всегда так (см. упр. 7.2А). Как мы знаем из раздела 5.3, можно добавить в алгоритм рандомизацию, чтобы получить хорошую ожидаемую производительность для всех входных данных. Многие считают такую рандомизированную версию алгоритма быстрой сортировки оптимальным выбором для обработки достаточно больших массивов. В разделе 5.3 рандомизация алгоритма проводилась путем явной перестановки его входных элементов.
В алгоритме быстрой сортировки можно было бы поступить точно так же, однако анализ упростится, если применить другой метод рандомизации, получивший название случайной выборки (гапбош зипрйпй). Вместо того чтобы в качестве опорного элемента всегда использовать А[т), такой элемент будет выбираться в массиве А[р .. т) случайным образом.
Подобная модификация, при которой опорный элемент выбирается случайным образом среди элементов с индексами от р до т, обеспечивает любому из т — р+ 1 элементов подмассива равную вероятность оказаться опорным. Благодаря случайному выбору опорного элемента можно ожидать, что разбиение входного массива в среднем окажется довольно хорошо сбалансированным. Изменения, которые нужно внести в процедуры РАкт1тюн и О111скзокт, незначительны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
