Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 24
Текст из файла (страница 24)
Как н при анализе программы Б, здесь А равно числу левосторонних минимумов, встречающихся при промежуточных операциях сортировки, а В равно числу инверсий в подмассивах. Основным фактором, от которого зависит время выполнения, является величина В, поэтому на нее мы в основном и обратим свое внимание. При анализе будет предполагаться, что ключи различны и первоначально расположены в случайном порядке. Назовем операцию шага П2 Ь-сортировкой. Тогда сортировка методом Шелла состоит из Ь1 1-сортировки, за которой следует Ь| т-сортировка, ..., за которой следует Ье-сортировка.
Массив, в котором К, < Кььь при 1 < 1 < Ю вЂ” Ь, будем называть Ь-упорядоченным. Рассмотрим сначала простейшее обобщение простых вставок, когда имеется всего два смещения: Ь~ — — 2 и Ье = 1. Во время второго просмотра имеем 2-упорядоченную последовательность ключей К~ Кт... Кл. Легко видеть, что число перестановок а~ от...а„множества (1,2,...,п), таких, что а, < а+э при 1 < 1 < и — 2, равно (и/2) так кэк существует всего одна 2-упорядоченная перестановка для каждого выбора (и/2) элементов, расположенных в четных позициях аз а4...; тогда остальные (и/21 элементов попадают в позиции с нечетными номерами.
После 2-сортировки случайного массива с одинаковой вероятностью может получиться любая 2-упорядоченная перестановка. Каково среднее число инверсий во всех таких перестановках? Пусть А„— суммарное число инверсий во всех 2-упорядоченных перестановках множества (1, 2,..., и), Ясно, что А1 = О, Аз = 1, Аэ = 2; рассмотрев шесть случаев 1324 1234 1243 2134 2143 3142, находим, что А4 = 1+ 0+ 1+ 1+ 2+ 3 = 8. Чтобы проанализировать А„в общем случае, рассмотрим "решетчатую диаграмму" на рис. 11 для н = 15.
На такой диаграмме 2-упорядоченную перестановку множества (1,2,...,и) можно представить в виде пути иэ верхней левой угловой точки (О,О) в нижнюю правую угловую зо ео Рис. 11. Соответствие между 2-упорядочением и путкмн на решетке. Курсивом набраны веса, соответсгвувпще числу инверсий в 2-упорядоченной перестановке. точку ((и/2), (и/2)), если выполнять очередной Ь-й шаг пути вправо или вниз в соответствии с тем, где находится й: в четной илн нечетной позиции перестановки. Этим правилом определяется взаимно однозначное соответствие между 2- упорядоченнымн перестановками н и-щаговыми путямн из одного угла решетчатой диаграммы в другой.
Например, изображенный на рпс. 11 путь соответствует перестановке 2 1 3 4 6 5 7 10 8 11 9 12 14 13 15. Далее, вертикальным отрезкам пути можно приписать веса, как показано на диаграмме; отрезку, ведущему из точки (1,у) в точку (1+1, у), приписывается вес р — Я. После несложных умозаключений читатель сможет убедиться в том, что сумма зтих весов вдоль каждого пути равна числу инверсий в соответствующей перестановке; эта сумма также равна количеству заштрихованных квадратиков между данным путем и другим ступенчатым путем, вьщеленным на рисунке пунктирной линией с жирными точками (см. Упр.
12). Так, например, перестановка (1) содержит 1+ О + 1+0+1+2+1+0=бинверсий. Если а < а' н Ь < Ь', то число допустимых путей из (а, Ь) в (а',Ь') равно числу способов объединения а' — а вертикальных отрезков с Ь' — Ь горизонтальными, а именно а' — а+ Ь' — Ь Следовательно, число перестановок, соответствующие пути которых проходят через вертикальный отрезок из ((,у) в (1+1, у), разно Умножая зто значение на вес данного отрезка и суммируя по всем отрезкам, полу- чаем Ой!за Знаки абсолютной величины в этих суммах несколько усложняют вычисления, но в упр.
14 показано, что выражение лля величины Ач имеет на удивление простой вид: 1в/2)2" '-. Следовательно, среднее число инверсий в случайной 2-упорядоченной перестановке равно (и/2) 2 По формуле Стирлиига эта величина асимптотически приближается к ~/и/Гаях/х 0.15пз/х. Как легко видеть, максимальное число инверсий равно Полезно более тщательно проанализировать распределение числа инверсий, ржсмотрев производящие функции ен(х) = 1, Ьт(х) = 1+х, Ьз(х) = 1+2х, Ь4(х) 1 + 2х + х + х как в упр, 15. Таким образом найдем, что стандартное отклонение тоже пропорционально пз)х, так что число инверсий не слишко:~ устойчиво распределено около среднего значения. Рассмотрим теперь общий случай алгоритма Р с двумя проходами, когда смещения сортировки равны Ь и 1.
Теорема Н. Среднее число инверсий в Ь-упорядоченной перестановке множества (1,2,...,и) равно л,ч='„„';,';((~)и и (;)а+с--,'(',') ). м где о= '1и/Ь) н с = паап'Ь, Эта теорема принадлежит Дугласу Х. Хвнту (Ропп!вв Н. НипЦ, [Васйе!ог'э йев!э, РПпсесоп Рп1чегх1су (Арг(1, 1967)). Заметим, что формула справедлива и при Ь > и и дает верный результат: /(и, Ь) = 1("). Докахагпельсгаво, В Ь-упорядоченной перестановке содержится г упорядоченных полпоследовательностей длиной д + 1 и Ь вЂ” г подпоследовательностей длиной а. Каждая инверсия образуется из элементов двух различных подпоследовательно- стей, а каждая пара различных упорядоченных подпоследовательностсй в случайной Ь-упорядоченной перестановке определяет случайную 2-упорядоченную перестановку. Поэтому среднее число инверсий равно сумме средних значений числа инверсий во всех парах различных подпоследовательностей, а именно (2) (2д~2) +' " (э~1) + ( 2 ) (и) Следствие.
Еглн посэедовательность смещений Ь| и ..., Ьы Ьо удовлетворяет ус- ловию (5) Ьмы п1об Ь, = 0 при 1 — 1 > э > О, то среднее число операций перезаписи в алгоритме 0 равно (г,/(4,+1, Ь,.„,/Ь,) + (Ь, — г,)/(о„, Ь,„.1/Ь,)), ~>в>о где г, = М той Ь„д, = (Х/Ь,), Ь, = ЮЬ, „а функция / онределлется форму- лой (4). Докаэогпельсшео. Процесс Ь;сортировки предусматривает сортировку методом простых вставок г, (Ь,+1/Ь,)-упорядоченных подмассивов длиной 4, + 1 и (Ь, — т,) таких подмассивов длиной о,.
Поскольку предполагается, что исходная перестановка случайна и все ее элементы различны, то пз условий делимости следует, что каждый из подмассивов — "случайная" (Ьмы/Ь,)-упорядоченная перестановка в том смысле, что все (Ьмы/Ь,)-упорядоченные перестановки равновероятны. ! Условие (5) этого следствия всегда выполняется для деухпроходнон сортировки методом Шелла, когда смещения равны соответственно Ь и 1, Пусть 4 = (Х/Ь), а г ы Х пюп Ь, тогда среднее значение величины В в программе 0 равно /(д+1,.Ч)+(Ь-г)/(4,Л)+/(Ь,Ь) =-"(4+ )+ ~' "~4)+/(Л,Ь). В первом приближении функция /(и, Ь) равна (~/~/8)нэ~эЬ'~э; можно сравнить ее с гладкой кривой на рис.
12 при и = 64. Следовательно, время выполнения двухпроходной программы 0 примерно пропорционально 2мэ/Ь + / узы Поэтому наилучшее значение Ь равно приблизительно (/18Х/л 1 72 4У; при таком выборе Ь среднее время сортировки пропорционально Ха~э. Таким образом, применяя метод Шелла н используя всежьнавсего два прохода, можно существенно сократить время по сравнению с методом простых вставок с О(Ю~) до О(Ж'жп). Ясно, что можно добиться лучших результатов, егчи использовать больше проходов. В упр. 18 обсуждается оптимальный выбор Ьт ы °,Ье при фиксированном 1 в случае, когда значения Ь ограничены условием делимости. Время выполнения при больших Х сокращается до О(Х' ьы/э), где е = 1/(2' — 1).
Используя приведенные выше формулы, барьер Хг в преодолеть невозможно, потому что на последнем проходе в сумму инверсий всегда входит слшвемое /(Х,Ь1) (чгя/8)Ж~~~Ь,~ 1100 пео ооо 400 зоо 2ОО 100 о ! В 16 24 22 40 46 06 64 72 ВО Л Рис. 12. Среднее число инверсий 2(и, Л) в Л-упорядочением массиве вз и элементов дла случая и = 64. Но интуиция подсказывает, что, если смещения Л~ и..., Ле ме будут удовлетворять условию делимости (5), можно достичь большего.
Например, при последовательном выполнении 8-, 4- и 2-сортировок невозможно взаимодействие между ключами в четных и нечетных позициях; поэтому иа долю заключительной 1-сортировки останется 9(Ю~~~) инверсий. В то же время при последовательном выполнении 7-, 5- и 3-сортировок массив перекомпоиовывается так, что при заключительной 1-сортировке не может встретиться более 2)ч' инверсий (см. упр. 26)! На самом деле наблюдается удивительное явление. Теорема К. После Л-сортировки й-упорядоченлый массив остается Л-упорядоченным, Таким образом, массив, который был сначала 7-рассортированным, а потом 5-рассортированным, становится одновременно 7- и 5-упорядочеииым.
А если подвергнуть его 3-сортировке„то полученный массив будет 7-, 5- и З-упорядоченным. Примеры проявления этого замечательного свойства можно найти в табл. 4. Доказательство. В упр. 20 показано, что эта теорема вытекает из следукнцей леммы. лемма ь. пусть т, и, г — неотрннвтельные целые числа, а (хы...,х„,ч.„) и (ры..., 0„4, ) — произвольные последовательности чисел, такце, что У! < Хп$+1Ф У2 < Хм+2 ° ° 1 93 < ХФЙ+Ф (7) Если последовательности хь н рь рассортировать независимо, так что х4 « "° Хм+г Н у1 « ' ' ри41 ~ 20 СООтЧОШЕННЯ (7) Оетаиуэся В СНЛЕ. Доказательства. Известно, что все, кроме, быть может, т элементов последовательности хь, превосходят (т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
