Алгоритмы - построение и анализ (1021735), страница 40

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 40)

Глава 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.

Сортировка и порядковая статистика 212 раза, полное юличество сравнений, выполняемых на протяжении работы алго- ритма, легко выразить следующим образом: Применяя к обеим частям этого выражения операцию вычисления математиче- ского ожидания и используя свойство ее линейности и лемму 5.1, получим: Е[Х] =Е и — 1 и ч. Е Ху 1=1 1=1+1 и-1 и — Е[Х;]= 1=1 1=1-~-1 и-1 и ,'> Рг(«; сравнивается с «). 17.2) 1=1 1=1+1 Осталось вычислить величину Рг(«; сравнивается с « ). Предполагается, что опорные элементы выбираются случайным образом, причем независимо друг от друга. Полезно поразмышлять о том, когда два элемента не сравниваются. Рассмотрим в качестве входных данных для алгоритма быстрой сортировки множество, состоящее из целых чисел от 1 до 10 (в произвольном порядке), и предположим, что в качестве первого опорного элемента выбрано число 7.

Тогда в результате первого вызова процедуры РАнт1т1ои все числа разбиваются на два множества: (1,2,3,4,5,6) и (8,9,10). При этом элемент 7 сравнивается со всеми остальными. Очевидно, что ни одно из чисел, попавшее в первое подмножество (например, 2), больше не будет сравниваться ни с одним элементом второго подмножества (например, с 9). В общем случае ситуация такая. Поскольку предполагается, что значения всех элементов различаются, то при выборе х в качестве опорного элемента впоследствии не будут сравниваться никакие «; и «, для которых «; < х < «у.

С другой стороны, если в качестве опорного выбран элемент «„то он будет сравниваться с каждым элементом множества Е,~, кроме себя самого. Аналогичное утверждение можно сделать по поводу элемента «;. В рассматриваемом примере значения 7 и 9 сравниваются, поскольку элемент 7 — первый из множества Ят э, выбранный в роли опорного. По той же причине (посюльку элемент 7 — первый из множества Яз э, выбранный в роли опорного) элементы 2 и 9 сравниваться не будут. Таким образом, элементы «; и «у сравниваются тогда и только тогда, когда первым в роли опорного в множестве Л1 выбран один из них.

Глава 7. Быстрая сортировка 213 Рг (я1 сравнивается с я ) = = Рг(Первым опорным элементом выбран г, или -.3) = Рг (Первым опорным элементом выбран я1] + + Рг (Первым опорным элементом выбран з,) = 1 1 2 + 3 †и 7 — г+1 1 †и (7.3) Сумма вероятностей в приведенной выше цепочке равенств следует из того, что рассматриваемые события взаимоисключающие.

Характеристики

Список файлов книги