Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 25
Текст из файла (страница 25)
е. больше или равны) некоторые элементы последо- вательиости у, причем различные элементы яэ превосходят различные элементы р. Пусть 1 < у < г. Так как после сортировки элемент х +г превосходит пг + / элементов яы то он превосходит, по крайней мере, у элементов у», а значит, ои превосходит у нагьиекьшпя элементов уы Следовательно, после сортировки имеем я+1>йг. $ ! Из теоремы К видно, что при сортировке желательно пользоваться взаимно простыми значениями смещений, однако непосредственно из нее не следуют точные оценки числа перезаписей, выполняемых алгоритмом В. Так как число перестановок множества (1,2,...,п), одновременно Ь- и Ь-упорядоченных, не всегда является делителем и1, то понятно, что теорема К объясняет далеко ие все; в результате Ь- и Ь-сортировок мекоторые й- и Ь-упорядоченные массивы получаются чаще других.
Более того, анализ усредненного варианта алгоритма В для общего случая смещений Ьг г,..., Ье при 1 > 3 может поставить в тупик любого. Не существует даже очевидного способа отыскать "наихудший случай" для алгоритма П при произвольной последовательности смещений сортировки (Ьг г,..., Ье) и заданном Х. Поэтому до сих пор все попытки анализа этого алгоритма в общем случае были тщетны. Но можно сделать определенные выводы из асимптотического поведения максимального времени сортировки, когда последовательность смещений имеет определенную форму.
Теорема Р. Если Ь, = 2г ы — 1 при 9 < в < Ф = '1!8 Х), то время сортггровки по алгоритму В есть 0(йз~г). Доказапгельспгво. Достаточно найти оценку В, — числа перезаписей на з-м проходе, такую, чтобы Вг г + - ° + Во = 0(Л~~~). Для первых 1/2 просмотров при Ф > в > 1/2 можно воспользоваться очевидной оценкой В, = 0(Ь,(Ю/Ь,)г), а для последующих проходов можно применить результат упр. 23: В, = 0(МЬ~+гЬг ы/Ь,). Следовательно, Вг-г+-"+Во = 0(Аг(2+2г+".+2ггг+2гуг+" +2)) = 0(Хзгг) Эта теорема принадлежит А. А.
Папернову и Г. В. Стасевичу 1Проблемы передачи информация, 1, 3 (1965), 81-98). Она дает верхнюю оценку времени выполнения алгоритма в худшем случае, а не просто оценку среднего времени работы. Этот результат нетривиален, поскольку максимальное время выполнения в случае, когда смещения Ь удовлетворяют условию делимости (5), имеет порядок ггг, а в упр. 24 доказано, чтб показатель 3/2 уменьшить нельзя. Интересное улучшение по сравнению с теоремой Р обиаружил в 1969 году Воган Пратт (Чапййап Ргагг). Если все смещения при сортировке выбираются иэ мншкества чисел вида 2э3", меньпшх Х, то время выполнения алгоритма В будет порядка Ж(1ой Ю) . В этом случае также можно внести в алгоритм иесколько существенных упрощений.
К сожалению, метод Пратта требует сравнительно большого числа проходов, так что это пе лучший способ выбора смещений, если только Ьт ие очень велико (см. упр. 30 и 31). При реальных для практики значениях Х наилучший набор значений смещеиий должен удовлетворять соотношению Ь, р", где параметр р Ь,г.г/Ь, можно в первом приближении считать независимым от в, но он существенно зависит от Х. Из изложенного выше очевидно, что было бы неразумно выбирать зиачения смещений, которые являются множителем всех предшественииков, Но в то же время нельзя делать заключение, что наилучшие зиачеивя смещений — взаимно простые числа всех предшественников.
Коиечно, каждый элемент массива, который уже ам аз, аз, ... = 3, 7, 16, 41, 101, 247, 613, 1529, 3821, 9539, ... После этого определяются смещения, если положить Ьо — — 1 н п1зн ~ ) <3< ~ ). Ьв = ле-г%. Таким образом, начальный участок последовательности смещений принимает вид 1; а~, аз, а~аз, а~аз азаз азазаз, ..., Например, прн р = 2.5 получим 1, 3, 7, 21, 48, 112, 336, 861, 1968, 4592, 13776, 33936, 86961, 198768,.... Решающим фактором в этом построении является возможность обратить рекур- рентное соотношение (8): (9) Таким образом, пользуясь аргументамн из предыдущего абзаца, получим, что число инверсий на элемент для Ье-, Ьмсортировкн и т. д.
равно по крайней мере Ь(аз, аз); Ь(аз, аз), Ь(аз, а~);Ь(аз, аз), Ь(аз, аз), Ь(аз, аз);..., (10) где Ь(Ыс) = -'(Ь вЂ” 1)(Ь вЂ” 1). Если р' ~ < Х < р', общее число перезаписей В не превосходит суммы первых 1 этой последовательности, умноженной на Л. Отсюда можно доказать, что в худшем случае время сортировки имеет порядок, значительно лучший, чем Л" з (см. упр.
41). Теорема 1. Время выполнения алгоритма О равно О~Хе"~'"и), если смещение Ь, определяются в соответствия с (8). Здесь с = з/81пр и ко ~сзаиты в О зависят отр, $ Эта асимптотическая верхняя граница не имеет существенного значения при Х -~ оо, поскольку последовательность, которую рекомендует Пратт, дает лучший результат. Рациональное же зерно теоремы 1 в том, что, если задано любое значение р > 1, последовательность смещений, имеющая практически показатель роста дй- и дй-рассортирован, причем Ь .1. Ь, имеет не более чем 1з(Ь вЂ” 1)(Й вЂ” Ц инверсий, когда наступает черед д-сортировки. (См. упр. 21.) Предложенная Праттом последовательность (2г3г) имеет при Ф -+ со преимущество именно вследствие этого свойства, но оно не очень сказывается на практике, поскольку нарастает это преимущество довольно медленно.
Дж. Инсерпи (Л. 1псегр1) и Р. Седгевик (К. Бе)йекбс)с) [см. Х Сошр. Яузц Яс1 31 (1985), 210-224; а также Ъесзпге Хотел 1п Сошр. Ясй 1136 (1996), 1-11) изобрели способ выбора лучшего варианта в том и другом смысле. Они показали, как сформировать последовательность смещений, для которых Л., ъ р', причем каждый очередной элемент в последовательности является наибольшим общим делителем своих предшественников. Задав любое значение р > 1, они далее определяли базовую последовашсльносшь ам аз, ..., где аз является наименьшим целым > р", таким, что а .~ аз при 1 < у < Ь. Если, например, р = 2:5, базовая последовательность имеет внд Таблица 5 АНАЛИЗ АЛГОРИТМА П ПРИ А' = В Смещения А,р,„, В,р,„. Я Т Время на НХХ Ь, р', может иметь время сортировки, которое гарантированно равно 0(Ф~+') при произвольных малых с > О.
Рассмотрим, каким на практике может быть значение М, для чего проанализируем общее время выполнения программы )З, а именно — 19В + 10ЮТ+ 1ЗТ— 10 — ЗА+ 1)и, В табл. 5 показано среднее время выполнения озртировки для различных последовательностей смещений при Ю = В. Заметим, что при таком малом значении Ю в общем времени выполнения преобладают вспомогательные операции, поэтому наилучшие результаты получаются при 1 = 1; следовательно, при Ф = 8 лучше всего пользоваться методом простых вставок. (Среднее время выполнения программы 5 при Ь' = 8 равно всего 191.85и.) Любопытно, что наилучший результат в двухпроходном алгоритме достигается при Ь1 = 6, поскольку большая величина Я оказывается важнее малой величины В. Аналогично три смещения, 3 2 1, минимизируют среднее число перезаписей, но это не самый лучший набор значений для трехпроходной сортировки. Быть может, интересно привести некоторые 'наихудшие" перестановки, максимизирующие число перезаписей, так как общий способ построения таких перестановок до снх пор не известен: Ьт = 5, Ь| = 3, Ье = 1: 85263741 119 перезаписей) Ьт = 3, Ь| = 2, Ье = 1: 83572461 (17 перезаписей) С ростом Ю наблюдаетси несколько иная картина.
В табл. 6 показаны приближенные значения числа перемещений для различных последовательностей смешений при )У = 1000. Первые несколько последовательностей удовлетворяют условию делимости 15), так что можно воспользоваться формулой (6) и упр. 19; для получения средних значений при других последовательностях смещений применялись эмпирические тесты. Были сгенерированы пять тысяч массивов по 1 ООО случайных элементов, н казидый массив сортировался с каждой последовательностью смещений.
Стандартное отклонение числа минимумов слева направо обычно составляло около 15, а стандартное отклонение числа перезаписей В обычно составляло около ЗОО. Эти данные позволяют выявить некоторые характеристики, но поведение алгоритма Хз все еще остается неясным. Шелл первоначально предполагал использовать смещения 1Х/2), 1Ж/41 „'1Х/81, ..., но это нежелательно, если двоичное предсгавле- 1.718 14.000 2 1 2.667 9,657 З 1 2.917 9ЛОО З.ОВЗ 1О.ООО 5 1 2.601 10.000 6 1 2.135 10,667 7 1 1.718 12.000 4 2 1 3.500 8.324 5 3 1 3.301 8.167 3 2 1 3.320 7.829 1 1 204.85и 3 2 235.91и 4 2 220.15и 5 2 217.75и б 2 209.20и 7 2 206.60и В 2 209.85и 7 3 274.42 и 9 3 253.60и б 3 280.50и Таблица б ДАННЫЕ О ВЫПОЛНЕНИИ АЛГОРИТМА О ПРИ Ас ж 1000 Смещеиия Асрсдд, Нсрсд .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
