AOP_Tom3 (1021738), страница 40
Текст из файла (страница 40)
Пусть о = (Ж/61, а г = Х шоп 6, тогда среднее значение величины В в программе П равно г/(Ч+1,~)+(6-г)/(й, 6)+/(6,6) =- —",('„')+', "(',)+/(1,6) В первом приближении функция /(и, 6) равна (1/в/8) ~э~э617~; можно сравнить ее с гладкой кривой на рис. 12 при и = 64. Следовательно, время выполнения двухпроходной программы В примерно пропорционально 2уэ/6+ ъЯ№ 6. Поэтому наилучшее значение 6 равно приблизительно ~/Г667/в - 1.72 ч'Ю: при таком выборе 6 среднее время сортировки пропорционально №7~.
Таким образом, применяя метод Шелла и используя всего-навсего два прохода, можно существенно сократить время по сравнению с методом простых вставок с О(№) до 0(№лв~). Ясно, что можно добиться лучших результатов, если использовать больше проходов. В упр. 18 обсуждается оптимальный выбор 6~ ы...,бв при фиксированном Г в случае, когда значения 6 ограничены условием делимости. Время выполнения при больших М сокращается до О(№ в г'~э), где е = 1/(2' — 1).
Используя приведенные выше формулы, барьер Х'ь преодолеть невозможно, потому что нв последнем проходе в сумму инверсий всегда входит слагаемое /(ж 6 ) ( Г /8) кы/261/э ыоо 1ООО 900 800 700 500 4ОО зоо гоо 1ОО о 1 8 16 24 32 40 48 56 64 72 80 Л Рис. 12. Среднее число инверсий 1(г!, Л) в Л-упорядоченном массиве нэ и элементов для случая и = 64. Но интуиция подсказывает, что, если смещения )!! 1,..., Ьа не будути удовлетворять условию делимости (5), можно достичь большего.
Например, при последовательном выполнении Я-, 4- и 2-сортировок невозможно взаимодействие между ключами в четных и нечетных позициях; поэтому на долю заключительной 1-сортировки останется 0(Ж~!~) инверсий. В то же время при последовательном выполнении 7-, 5- и 3-сортировок массив перекомпоновывается так, что при заключительной 1-сортировке не может встретиться более 2% инверсий (см. упр. 26)! На самом деле наблюдается удивительное явление. Теорема К. После й-сортлровки 74-упорядоченный массив остается й-упорядоченным. Таким образом, массив, который был сначала 7-рассортированным, а потом 5-рассортированным, становится одновременно 7- и 5-упорядочениым. А если подвергнуть его З-сортировке, то полученный массив будет 7-, 5- и З-упорядоченным.
Примеры проявления этого замечательного свойства можно найти в табл. 4. Дакаэа7лельси4ва. В упр. 20 показано, что эта теорема вытекает иэ следующей леммы. Лемма Ь. Пусть п4, н, г — - неотрицательные целые числа, а (х1,...,х +,) и (у1,..., у„+,) — про!гзвольные последовательности чисел, такие, что У! ~ Х|л!.1 У2 ~ 2'ы-!-2; ~ Уг ~ Хпь+г ° (7) Если последовательности хл и ул рассортировать независимо, гвк что х, ( ..
( х„,+„н у, ( -. < у„+„, то соотношения (7) останутся в силе. Доказан!ельс7пва. Известно, что все, кроме, быль может, гл элементов последовательности хл, превосходят (т. е. больше или раины) некоторые элементы последо- вательности у, причем различные элементы хь превосходят различные элементы у. Пусть 1 < у < г.
Так как после сортировки элемент т чу превосходит т+ у элементов хю то он превосходит, по крайней мере, у' элементов уы а значит, он превосходит у наименьших элементов уь. Следовательно, после сортировки имеем х ч. > уу. $ Из теоремы К видно, что прн сортировке желательно пользоваться взаимно простыми значениями смещений, однако непосредственно из нее не следуют точные оценки числа перезаписей, выполняемых алгоритмом В. Так как число перестановок множества (1,2,...,и), одновременно А- и к-упорядоченных, не всегда является делителем и!, то понятно, что теорема К объясняет далеко не все; в результате йи Л-сортировок некоторые Й- н 6-упорядоченные массивы получаются чаще других.
Более того, анализ усредненного варианта алгоритма В для общего случая смещений 1ч ы..., Ьв при г > 3 может поставить в тупик любого, Не существует даже очевидного способа отыскать "наихудший случай" для алгоритма В при произвольной последовательности смещений сортировки (1о ы..., Ьо) и заданном Ж. Поэтому до сих пор все попытки анализа этого алгоритма в общем случае были тщетны.
Но можно сделать определенные выводы из асимптотического поведения максимального времени сортировки, когда последовательность смещений имеет определенную форму. Теорема Р. Если А, = 2'+1 — 1 прн 0 < в < Ф = (18%), то время сортировки по алгоритму В есть 0(Хз~з). Доказатвельсшво. Достаточно найти оценку В, — числа перезаписей на а-м проходе, такую, чтобы В1 1+ . + Во — — 0(Юз~з). Для первых 1/2 просмотров при Ф > а > 1/2 можно воспользоваться очевидной оценкой В, = 0(14(аб/А,)т), а для последующих проходов можно црнмеиить результат упр.
23: В, = 0(йй,~.зп„+1/и,). Следовательно, В~, +. +Во — — 0(Ю(2+2 +..+2'~я+2'~э+ +2)) = 0(Ж~~з). 1 Эта теорема принадлежит А. А. Папернову и Г. В. Стасевичу (Проблемы передачи информации, 1, 3 (1965), 81-98). Она дает верхнюю оценку времени выполнения алгоритма в худшем случае, а не просто оценку среднего времени работы. Этот результат нетрнвивлеи, поскольку максимальное время выполнения в случае, когда смещения А удовлетворяют условию делимости (5), имеет порядок Жт, а в упр. 24 доказано, что показатель 3/2 уменьшить нельзя.
Интересное улучшение по сравнению с теоремой Р обнаружил в 1969 году Воган Пратт (ЧапбЬап Ргали. Если все смещения нрн сортировке выбираются оз множества чисел вида 2г3х, меньших Х, то время выоолненн» алгоритма В будет порядка Ф(1ой Х)з. В этом случае также можно внести в алгоритм несколько существенных упрощений. К сожалению, метод Пратта требует сравнительно большого числа проходов, так что это не лучший способ выбора смещений, если только Х не очень велико (см. упр.
30 и 31). Прн реальных для практики значениях Ю наилучший набор значений смещений должен удовлетворять соотношению 6, ж р", где параметр р ж Ат ы/й, можно в нервом приближении считать независимым от в, но он существенно зависит от )х'. Из изложенного выше очевидно, что было бы неразумно выбирать значения смещений, которые являются множителем всех предшественников. Но в то же время нельзя делать заключение, что наилучшие значения смещений — взаимно простые числа всех предшественников.
Конечно, каждый элемент массива, который уже дЬ- и дй-рассортирован, причем Ь 1 Ь, имеет не более чем -'(Ь вЂ” 1)(й — 1) инверсий, когда наступает черед д-сортировки. (См. упр. 21.) Предложенная Праттом последовательность (2е3з) имеет при Х -+ оо преимущество именно вследствие этого свойства, но оно не очень сказывается на практике, поскольку нарастает это преимущество довольно медленно. Дж. Инсерпи (Л. 1псегр1) и Р.
Седгевик (К, Зеббен1с)с) [см. Х Сопзр. Яувс. Ясй 31 (1985), 210-224; а также 1есгпге №Зез ш Сошр. Яс1. 1136 (1996), 1-11] изобрели способ выбора лучшего варианта в том и другом смысле. Они показали, как сформировать последовательность смещений, для которых Ь, - р', причем каждый очередной элемент в последовательности является наибольшим общим делителем своих предшественников. Задав любое значение р > 1, они далее определяли базовую последоеазпельность аы аз, ..., где аь является наименьшим целым > у, таким, с что ау 1 аь при 1 < з < 1с. Если, например, р = 2.5, базовая последовательность имеет вид аы аз, аз, ...
— — 3, 7, 16., 41, 101., 247, 613, 1529, 3821, 9539, После этого определяются смещения, если положить Ье = 1 и Ь,=Ь,,а, прн ( )<в<( ). (8) Таким образом, начальный участок последовательности смещений принимает вид 1; а,; аз, азат; азаз, азаз, азазаз; . .. Например, при р = 2.5 получим 1, 3, 7, 21, 48, 112, 336, 861, 1968, 4592, 13776, 33936, 86961, 198768,....
Решающим фактором в этом построении является возможность обратить рекур- рентное соотношение (8): при < в < Ь, = Ь„,/а, = Ь(.)/а(.) (9) Таким образом, пользуясь аргументами из предыдущего абзаца, получим, что число инверсий на элемент для Ье-, Ьпсортировки и т. д. равно по крайней мере Ь(аз, а,); Ь(аз, аз), Ь(аз, аз); Ь(а4, аз), Ь(аз, аз), Ь(ез, аз);..., (10) где Ь(Ь,Ь) = -'(Ь вЂ” 1)(Ь вЂ” 1). Если р' ' < Х < р', общее число перезаписей В не превосходит суммы первых 1 этой последовательности, умноженной на Ю. Отсюда можно доказать, что в худшем случае время сортировки имеет порядок, значительно лучший, чем Х" (см. упр, 41).
Эта асимптотическая верхняя граница не имеет существенного значения при Ьд -+ оо, поскольку последовательность, которую рекомендует Пратт, дает лучший результат. Рациональное же зерно теоремы 1 в том, что, если задано любое значение р > 1, последовательность смещений, имеющая практически показатель роста Теорема 1. Время выполнения алгоритма О равно О(/де' мп), если смещения Ь, определяются в соответствия с (8). Здесь с = у'8!пд и константы в О зависят от р. Таблица 5 АНАЛИЗ АЛГОРИТМА Гз ПРИ Аг = 8 Смещения А,р,„„, В„„, Я Т Время на Н1Х гг, ж р', может иметь время сортировки, которое гарантированно равно 0(Аг~+') при произвольных малых г > О.
Рассмотрим, каким на практике может быть значение Аг, для чего проанализируем общее время выполнения программы П, а именно — (9В+ 10АгТ+ 13Т— 105 — ЗА + 1)и. В табл. 5 показано среднее время выполнения сортировки для различных последовательностей смещений при гг' = 8. Заметим, что при таком малом значения Аг в общем времени выполнения преобладают вспомогательные операции, поэтому наилучшие результаты получаются прн Г = 1; следовательно, при Аг = 8 лучше всего пользоваться методом простых вставок. (Среднее время выполнения программы Я при Х = 8 равно всего 191.85и.) Любопытно, что наилучший результат в двухпроходном алгоритме достигается при Ьг — — 6, поскольку большая величина В оказывается важнее малой величиньг В, Аналогично три смещения,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
