Структуры данных и алгоритмы (1021739), страница 60
Текст из файла (страница 60)
В качестве первого шага в доказательствеобоих утверждений надо показать, что время выполнения процедуры partition^, j, v)238ГЛАВА 8. СОРТИРОВКАимеет порядок O(j - i + 1), т.е. пропорционально числу элементов, над которымиона выполняется.Чтобы "разобраться" с временем выполнения процедуры partition, воспользуемсяприемом, который часто применяется при анализе алгоритмов.
Надо найти определенные "элементы", для которых в принципе можно вычислить время выполнения, азатем необходимо показать, что каждый шаг алгоритма для "обработки" одного"элемента" требует времени, не превышающего константы. Тогда общее время выполнения алгоритма можно вычислить как произведение этой константы на количество "элементов".В данном случае в качестве "элементов" можно просто взять элементы A[i], ...,A\J] и для каждого из них оценить время, необходимое для достижения в процедуреpartition курсорами I и г этого элемента, начиная от исходного положения этих курсоров.
Сначала отметим, что эта процедура всегда возвращает значение курсора, разбивающее множество элементов A[i], ..., АЦ] на две группы, причем каждая из этихгрупп содержит не менее одного элемента. Далее, так как процедура заканчиваетсятолько тогда, когда курсор / "перейдет" через курсор г, то отсюда следует, что каждый элемент просматривается процедурой хотя бы один раз.Перемещение курсоров осуществляется в циклах строк (4) и (6) листинга 8.7 путем увеличения на 1 значения I или уменьшения на 1 значения г. Сколько шаговможет сделать алгоритм между двумя выполнениями оператора 1:= 1 + 1 или оператора г:= г - 1? Для того чтобы смоделировать самый худший случай, надо обратиться к началу процедуры.
В строках (1), (2) происходит инициализация курсоров { и г .Затем обязательно выполняется перестановка элементов в строке (3). Далее предположим, что циклы строк (4) и (6) "перескакивают" без изменения значений курсоров Iи г. На втором и последующих итерациях цикла repeat перестановка в строке (3) гарантирует, что хотя бы один из циклов while строк (4) и (6) будет выполнен не менееодного раза.
Следовательно, между выполнениями оператора /:= / + 1 или п= г - 1 всамом худшем случае выполняются строки (1), (2), дважды строка (3) и проверки логических условий в строках (4), (6), (8) и снова в строке (4). Все эти операции требуют фиксированного времени, независящего от значений i и /.В конце исполнения процедуры выполняются проверки в строках (4), (6) и (8), несвязанные ни с какими "элементами", но время этих операций также фиксировано ипоэтому его можно "присоединить" к времени обработки какого-либо элемента.
Извсего вышесказанного следует вывод, что существует такая временная константа с,что на обработку любого элемента затрачивается время, не превышающее с. Поскольку процедура partition(i, j, v) обрабатывает j - i + 1 элементов, то, следовательно, общее время выполнения этой процедуры имеет порядок О(/ - i + 1).Вернемся к оценке времени выполнения процедуры quicksort(i, j).
Легко проверить, что вызов процедуры findpivot в строке (1) листинга 8.8 занимает время порядка O(j - i + 1), а в большинстве случаев значительно меньше. Проверка логическогоусловия в строке (2) выполняется за фиксированное время, так же, как и оператор встроке (3), если, конечно, он выполняется. Вызов процедуры partition(i, j, pivot), какмы показали, требует времени порядка O(j - i + 1).
Таким образом, без учета рекурсивных вызовов quicksort каждый отдельный вызов этой процедуры требует времени,по крайней мере пропорционального количеству элементов, упорядочиваемых этимвызовом quicksort.Если посмотреть с другой стороны, то общее время выполнения процедурыquicksort является суммой по всем элементам количества времени, в течение которого элементы находятся в части массива А, обрабатываемой данным вызовом процедуры quicksort.
Вернемся к рис. 8.1, где вызовы процедуры quicksort показаныпо этапам (уровням). Очевидно, что никакой элемент не может участвовать в двухвызовах процедуры quicksort на одном уровне, поэтому время выполнения даннойпроцедуры можно выразить как сумму по всем элементам определенной глубины,т.е. максимального уровня, на котором заканчивается сортировка для данного эле8.3.
БЫСТРАЯ СОРТИРОВКА239мента. Например, из рис. 8.1 видно, что элемент 1 является элементом глубины 3,а элемент 6 — глубины 5.Чтобы реализовать самый худший случай выполнения процедуры quicksort, мы должны управлять выбором опорного элемента, например выбрать в качестве опорного значения наибольшее значение ключа в сортируемом множестве элементов.Тогда сортируемое множество элементов разбивается на дваподмножества, одно из которых содержит только один элемент(ключевое значение этого элемента совпадает с опорным значением). Такая последовательность разбиения исходного множества приводит к структуре дерева, подобного изображенному нарис. 8.3, где записи г\, г2г„ заранее упорядочены в порядкевозрастания ключей.В приведенном примере элемент rt (2 < i < п) имеет глубинуп - i - 1, а глубина элемента rl составляет л - 1.
Сумма глубинэлементов равна_^пРис. 8.3. Наихудшая возможная последовательность т е имеет ПОрЯдОК П(И2). Таким образом, показано, что времявыоорапарны выполнения алгоритма быстрой сортировки п элементов в самомэлементовхудшем случае пропорционально п2.Время выполнения быстрой сортировки в среднемКак всегда, выражение "время выполнения в среднем" понимается как усреднение времени выполнения сортировки по всем возможным упорядочениям исходныхнаборов элементов в предположении, что все упорядочения равновероятны. Для простоты также предположим, что не существует записей с одинаковыми ключами.
Вобщем случае при возможном равенстве значений некоторых ключей анализ временивыполнения также осуществляется сравнительно просто, но несколько по-иному.Сделаем еще одно предположение, которое тоже упрощает анализ. Будем считать,что при вызове процедуры quicksort(i, j) все упорядочивания элементов -A[i], ..., A[j]равновероятны.
Это предположение можно попытаться обосновать исходя из тогоочевидного факта, что опорное значение и, примененное в предыдущем вызовеquicksort, нельзя использовать для разбиения данного подмножества элементов, таккак здесь все элементы имеют значения ключей либо меньшие v, либо большие, либоравные и.1 Более тщательный анализ программы быстрой Сортировки показывает,что предыдущий опорный элемент скорее всего будет находиться возле правого концаподмножества элементов, равных или больших этого опорного значения (т.е. не будетнаходиться с равной вероятностью в любом месте этого подмножества), но для больших множеств этот факт не имеет определяющего значения.2Обозначим через Т(п) среднее время, затрачиваемое алгоритмом быстрой сортировки на упорядочивание последовательности из п элементов.
Очевидно, что времяТ(1) равно некоторой константе с\, поскольку имеется только один элемент и не ис1Конечно, порядок элементов A[i], ..., A\j] будет зависеть от первоначального упорядочивания элементов А[1], ..., А[п] и от ранее выбранных опорных элементов (см.
в тексте следующеепредложение и следующий абзац). Но основываясь на предположении о равных вероятностяхвсех упорядочений исходной последовательности элементов и на том факте, что предыдущееопорное значение влияет на количество и состав элементов A[i]A[j], но мало влияет на ихвзаимное расположение, в первом приближении гипотеза о равновероятности всех упорядочений элементов A[i], ..., АЦ] выглядит вполне приемлемой. — Прим. ред.Из приведенных рассуждений можно сделать практический вывод: если сортировка выполняется не так быстро, как ожидалась, то можно предварительно переупорядочить сортируемые элементы в случайном порядке, а затем повторить быструю сортировку.240ГЛАВА 8. СОРТИРОВКАпользуется рекурсивный вызов процедуры quicksort самой себя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
