Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 41
Текст из файла (страница 41)
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, г) Этот алгоритм будет проанализирован в следующем разделе.
Глава 7. Быстрая сортировка 209 Упражнения 7.3-1. Почему производительность рандомизированного алгоритма анализируется в среднем, а не в наихудшем случае? 7.3-2. Сколько раз в ходе выполнения процедуры Клноом~кноЯглскзокт в наихудшем случае вызывается генератор случайных чисел Клипом? 7.4 Анализ быстрой сортировки В разделе 7.2 были приведены некоторые интуитивные рассуждения по поводу поведения алгоритма быстрой сортировки в наихудшем случае, и обосновывалось, почему следует ожидать достаточно высокой производительности его работы. В данном разделе проведен более строгий анализ поведения этого алгоритма. Начнем этот анализ с наихудшего случая.
Подобный анализ применим как к процедуре Оглскзокт, так и к процедуре КАноом~гвоЯглскзокт. В конце раздела анализируется работа процедуры КАноомывоЯглскзокт в среднем случае. 7.4.1 Анализ в наихудшем случае Т(п) = шах (Т(д) + Т(п — д — 1)) + 0(п), 0<я<в-1 (7.1) где параметр д изменяется в интервале от О до п — 1, поскольку на выходе проце- дуры РАкт!т!Ох мы получаем две подзадачи, полный размер которых равен и — 1. Мы предполагаем, что Т(п) < сиз для некоторой константы с. Подставляя это неравенство в рекуррентное соотношение (7.1), получим Т (и) < шах (сд + с(п — д — 1) ) + 9 (и) = о<я< -1 = с шах (дз + (и — 1 — д) ) + 0 (и).
о<я< -1 Выражение уз+ (и — д — 1) достигает максимума на обоих концах интервала О < д < и — 1, что подтверждается тем, что вторая производная от него по В разделе 7.2 было показано, что при самом неудачном разбиении на каждом уровне рекурсии время работы алгоритма быстрой сортировки равно О (на). Интуитивно понятно, что это наихудшее время работы рассматриваемого алгоритма.
Докажем это утверждение. С помощью метода подстановки (см. раздел 4.1) можно показать, что время работы алгоритма быстрой сортировки равно О (пз). Пусть Т (и) — наихудшее время обработки процедурой Оглскзонт входных данных размером и. Тогда мы получаем следующее рекуррентное соотношение: Часть П. Сортировка и порядковая статистика 210 д положительна (см. упражнение 7.4-3). Это наблюдение позволяет нам сделать следующую оценку: шах (т7 + (и — д — 1) ) < (и — 1) = и — 2п + 1. о<я< -1 ~ В результате получаем следующее ограничение для Т (п): Т (и) < сп — с (2п — 1) + 9 (п) < спз, поскольку константу с можно выбрать настолько большой, чтобы слагаемое с(2п — 1) доминировало над слагаемым 6 (и).
Таким образом, Т (и) = О (пз). В разделе 7.2 мы встречались с частным случаем быстрой сортировки, при котором требовалось время П (пз) — это случай несбалансированного разбиения. В упражнении 7.4-1 нужно показать, что рекуррентное соотношение (7.1) имеет решение Т(п) = П (пз). Таким образом, время работы алгоритма быстрой сортировки (в наихудшем случае) равно 6 (п~). 7.4.2 Математическое ожидание времени работы Мы уже приводили интуитивный аргумент в пользу того, что время работы процедуры КАмпомынп Отлскзокт в среднем случае равно 0 (п1бп): если на каждом уровне рекурсии в разделении, производимом процедурой КАхпОМ~~еп Рлкт|7~0н, в одну часть массива помещается произвольная фиксированная доля элементов, то высота рекурсивного дерева равна 0(1бп), а время работы каждого его уровня — О (и). Даже после добавления новых уровней с наименее сбалансированным разбиением время работы останется равным 0 (п1бп).
Можно провести точный анализ математического ожидания времени работы процедуры КАнпомяеп Оискзокт. Для этого сначала нужно понять, как работает процедура разбиения, а затем — получить для математического ожидания времени работы оценку 0 (и 1к и) в предположении, что значения всех элементов различны. Эта верхняя граница математического ожидания времени работы в сочетании с полученной в разделе 7.2 оценкой для наилучшего случая, равной 9 (п1бп), позволяют сделать вывод о том, что математическое ожидание времени работы равно 0 (п1кп).
Время работы и сравнения Время работы процедуры Ощскзокт определяется преимущественно временем работы, затраченным на выполнение процедуры РАкт~т)ои. При каждом выполнении последней происходит выбор опорного элемента, который впоследствии не принимает участия ни в одном рекурсивном вызове процедур Оглскзокт и Рлкт~тюм. Таким образом, на протяжении всего времени выполнения алгоритма Глава 7. Быстрая сортировка 211 быстрой сортировки процедура РАкт~тюн вызывается не более и раз. Один вызов процедуры РАкт)тюк выполняется в течение времени О (1), к которому нужно прибавить время, пропорциональное количеству итераций цикла (ог в строках 3-6.
В каждой итерации цикла (ог в строке 4 опорный элемент сравнивается с другими элементами массива А. Поэтому, если известно количество выполнений строки 4, можно оценить полное время, которое затрачивается на выполнение цикла 1ог в процессе работы процедуры Яиккзокт. Лемма 7.1. Пусть Х вЂ” количество сравнений, которое выполняется в строке 4 процедуры Рлкт~тюм в течение полной обработки п-элементного массива процедурой Яискзокт.
Тогда время работы процедуры Опскзокт равно О (и + Х). Доказательство. Как следует из приведенных выше рассуждений, процедура РАкт~тюм вызывается и раз, и при этом производится определенный фиксированный обьем работы. Затем определенное число раз запускается цикл 1ог, при каждой итерации которого выполняется строка 4. Таким образом, наша цель — вычислить величину Х, т.е. полное количество сравнений, выполняемых при всех вызовах процедуры РАкт~тюм. Не будем пытаться проанализировать, сколько сравнений производится при каждом вызове этой процедуры.
Вместо этого получим общую оценку полного количества сравнений. Для этого необходимо понять, в каких случаях в алгоритме производится сравнение двух элементов массива, а в каких — нет. Для упрощения анализа переименуем элементы массива А как зм зз,..., з„, где гч — 1-й наименьший по порядку элемент. Кроме того, определим множество Я; = (г,, я,+ы..., я ), которое содержит элементы, расположенные между элементами гн и з включительно. В каких случаях в алгоритме производится сравнение элементов гн и з ? Прежде чем ответить на этот вопрос, заметим, что сравнение каждой пары элементов производится не более одного раза.
Почему? Дело в том, что элементы сравниваются с опорным, который никогда не используется в двух разных вызовах процедуры РАкт]тюм. Таким образом, после определенного вызова этой процедуры используемый в качестве опорного элемент впоследствии больше не будет сравниваться с другими элементами. Воспользуемся в нашем анализе индикаторными случайными величинами (см. раздел 5.2). Определим величину Х; = 1(я, сравнивается с з;), с помощью которой учитывается, произошло ли сравнение в течение работы алгоритма (но не в течение определенной итерации или определенного вызова процедуры РАкт1тюм). Поскольку каждая пара элементов сравнивается не более одного Часть 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
