Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 35
Текст из файла (страница 35)
Перейти к шагу К4„если он равен О. и: >>>~у~> > > — >. >>4=>-ц Перейти к шагу Кб, если 1 < 1. (г14=1-1] КЯ. П ве ять наличие 0 я Младший разряд тА >- разряд Ь ключа Ктеь Перейтн к шагу Кб, если ои равен 1. 1. Номе >ять мес ами В. 88 ВН ЛЕ оу 81 РЕСБ 1 А А — С А — число итераций, в которых 1 < г;  — число операций обмена записей; С = С'+ Св — число проверок разрядов: С вЂ” число случаев, когда Ь > т на шаге КВ; К вЂ” число случаев, когда Ь < т, г = 1 на шаге ВН; Ь вЂ” число случаев, когда Ь < т, 1' < 1 на шаге КВ;  — число случаев, когда Ь < т, ) = г на шаге КВ; Я вЂ” число случаев, когда что-либо пол~ещается в стек; Х вЂ” число случаев, когда 1 < 1 на шаге Кб. (29) По закону Кирхгофа 5 = А — 6 — К вЂ” Х вЂ” В, так что аб1цее время выполнения равно 27А + 8В + НС вЂ” 23С вЂ” 14К вЂ” 17Š— 19 — Л + 13 машинных циклов.
За счет усложнения программы можно несколько ускорить циклы проверки разрядна (см. упр, 34). Обменную поразрядную сортировку можно также ускорить, если при достаточно малых значениях разности г — 1 применять простые вставки, как это сделано в алгоритме Ц, но мы не будем задерживаться на таких усовершенствова- ниях. Проанализируем время выполнения обменной поразрядной сортировки в двух случаях„которым соответствуют разные наборы условий. 1) Пусть Ф = 2 и ключи, которые следует рассортировать, — просто числа О, 1, 2, ..., 2™ — 1, расположенные в случайном порядке, й) Пусть т = оо (неограниченная точность) и ключи, которые необходимо рассортировать, — нтависимые, равномерно распределенные в промежутке (О .. 1) действительные числа.
Анализ случая (!) относительно прост, поэтому он оставлен читателю в качестве упражнения (см. упр. 35). Случай (й) более сложен, но его мы также оставили для упражнений. В следующей таблице приведены грубые оценки результатов анализа в том и другом случаях. 88 ЕИТ4 -1,3 А — С 88 РЕС4 0,2 А — С 84 84Е 18 А — С 88 РЕС4 0,1 А — С вЂ” К 8б 84 И 1В А — С вЂ” К 87 14ИЕ 9В А-С-0 — К 88 1ИС1 1 К 88 2Н 11ИЕ 1В К+Я 48 0Н ЕИТ1 1,2 8+1 41 102 БТАСН,6(А) Я+ 1 48 РЕС1 0,2 8+ 1 48 1Э6 БТАСК,6(В) Я + 1 РЕС6 1 9+1 45 86ИИ 2В 8+1 Время работы программы обменной ющих показателей; К8.П ве ить особые гл чви, г14 неизвестна) Перейти к шагу К10, если Ь = т, иначе — Ь +- Ь вЂ” 1.
г14+- з) г14 +- 8 — г. Перейти к шагу К2, если 1 = г. г14 ь- З вЂ” А Перейти к вагу К2, если 1 < А Перейти к шагу К9, если У;Ь Ь 1+-1+ 1. Переход, если 1 ~ г. КПЬ Изаве ен е нз стека. Отек =ь (г,Ь). Перейтн к шагу К2, если стек не пуст. 3 поразрядной сортировки зависит от следу- Величина А В С С К б В Я Х Случай (!) К -'г7 16 й7 Х1кК ,-'л 0 0 0 —,'К йл 2 Случай (й) оК 14Х!яИ К!йХ 0 -',л $(о — 1)И з (а — 1)!!! —,'К ф(о+ 1)л! Здесь а = 1~ 1п 2 1.4427. Заметим, что среднее число обменов, проверок разрядов и обращений к стеку, по существу, одинаково в обоих случаях, несмотря даже на то, что в случае (й) число итераций на 44% больше.
На сортировку К элементов в случае (й) наша й1Х-программа затратит в среднем приблизительно 14.4 К 1п й! машинных циклов. Это число можно сократить примерно до 11.5 К!п Ж, если воспользоваться предложением из упр. 34. Соответствующая величина для программы (4 равна 11.7 Ф 1п Ф, но и ее можно уменьшить до 10.6 К 1п Ф, если воспользоваться предложением Синглтона и выбрать медиану из трех ключей. В случае равномерного распределения данных обменная поразрядная сортировка отнимает в среднем примерно столько же времени, сколько и быстрая сортировка; иа некоторых компьютерах она выполняется немного быстрее, чем быстрая сортировка. В упр. 53 показано, в какой мере замедляется этот процесс при неравномерном распределении.
Важно отметить, что весь наш анализ основан на предположении о том, что все клн~чи различны, Обменная поразрядная сортировка в таком виде, как описано выше, не очень эффективна, если имеются одинаковые ключи, поскольку она проходит через несколько итераций, каждая нз которых требует определенного времени для разделения множества одинаковых ключей до тех пор, пока Ь не станет > гп.
Один приемлемый способ исправления этого недостатка предложен в ответе к упр. 40. Как обменная поразрядная сортировка, так и быстрая сортировка основаны на идее разбиения. Записи меняются местами до тех пор, пока массив не будет разбит на две части: левый подмассив„в котором все ключи ( К прн определенном К, и правый подмассив, в котором все ключи > К, При быстрой сортировке в качестве К выбирается реальный ключ из массива, в то время как при обменной поразрядной сортировке, по существу, выбирается некоторый искусственный ключ на основе двоичных представлений. Что касается исторической стороны дела, то обменную поразрядную сортировку открыли П.
Хильдебрандт, Г. Исбитц. Х. Райзинг и Ж. Шварц !см, Р. Н!!6еЬгапг)г, Н. 1зЬЬз, Н. Н!з!пй, д. ЯсЬпаггз,,ИСМ 6 (1959)„ 156-.163] примерно за год до изобретения быстрой сортировки. Существуют и другие схемы разделения; например, Джон Мак-Карти (ЯоЬп МсСаггЬу) предложил выбирать К -'(и+и), если известно, что все ключи находятгл в диапазоне между и и е. Еще одну стратегию разделения предложил М. Х. ван Эмден (М. Н. гап Епк1еп) !САСМ 13 (1970), 563-567): вместо того чтобы выбирать К заранее, мы "узнаем", каким может быть хорошее значение К, отслеживая в процессе разделения изменение величин К' = пих(Кь..., К;) и К" = ш(п(К~,..., К,). Можно увеличивать 1 до тех пор, пока не встретится ключ, больший К', а затем начать уменьшать у, пока не встретится юпоч, меньший К", после чего поменять их местами я/или уточнить значения К' и К".
Эмпирические тесты этой "интервальной сортировки с обменом" показывают„что она осуществляется несколько медленны„чем быстрая, а тчюретический анализ выполнить очень сложно. В значительной мере затруднение во время анализа вызывает тот факт, что записи в подмассивах после разделения ух<е нельзя считать размещенными в случайном порядке. Это единственный метод, обсуждаемый в данной книге, для поведения которого еще не найдено адекватного теоретического объяснения. Обобщение обменной поразрядной сортировки для системы счисления с основанием, болыпим 2, обсуждается в разделе 5.2.5. вАсммптотическне методы. Анализ алгоритмов обменной сортировки приводит к некоторым особенно поучительным математическим задачам„которые позволяют больше узнать о способах определения асимптотического поведения функции.
Например, при анализе метода пузырька (формула (9)) мы столкнулись с функцией И'„= —, ~ в)г" '. (31) Ой~<э<в Какой внд имеет асимптотическое выражение для этой Функции? Можно действовать так же, как при исследовании числа инволюций (формула 5.1.4-(41)]. Поэтому, прежде чем двигаться дальше, полезно еще раз просмотреть материал, изложенный в конце раздела 5.1.4.
Исследование формулы (31) показывает, что вклад при з = и больше, чем вклад прн в = и — 1 и т. д. Это наводит на мысль о замене э на и — в. Мы скоро увидим, что на самом деле удобнее всего применить подстановки 1 = и — в+1, т = и+ 1, в результате которых формула (31) примет вид — И = 1 ~~~ (т — 1)! 1 (32) т гп! ' 1<С<т обдаст-ь Для внутренней суммы существует хорошо известный асимптотический ряд, полученный из формулы суммирования Эйлера: 1 $ г = — — — (Х вЂ” бп) + — (1 — 1)(К вЂ” бш) + ".
Вз г-в 2- 21 в<с<я — ( . ) В„(Ж' У вЂ” 4, ) + 0(Х' ~) т=о (см. упр. 1.2.11.2 — 4). Следовательно, наша задача сводится к анализу сумм вида — ( — 1).'(гп — 1) гь, к > — 1. (34) ' ~бю< ь Как и в разделе 5.1.4, можно показать„что при значениях 1, больших гп'~в+', члены суммы пренебрежимо малы: 0(ехр(-пз)). Значит, можно положить 1 = 0(гл'~э+') и заменить факториалы по формуле Стнрлинга: Фз Фз $4 гь 2гп 3гпт 4гпз бгп" у / = ~/1- — ехр~ га ~ 12тт Таким образом нас интересует асимптотическое выражение для суммы гь(гп) = ~~~ е /"""г, Й > -1.
(35) ~<с< л (С мирование здесь также можно было бы распространить на вгкь диапазон 1 < умми 1< ао,неизмен р ив при этом значения аснмптотического выражения суммы, посколь'~з+' и еб жиче ку, как указано выше, входящие в сумму значения при $ > т' +' пренебрежимо Пусть уь(х) = а"е-*' и /ь(х) = уь(я/~/2т). По формуле суммирования Эйлера при й > 0 получим Следовательно, при помощи, по существу, тех же приемов, которые применялись н раньше, можно получить асимптотичесхий ряд лля гь(гп), если тол . р ько к > О.
Но п и и = -1 этот метод не годится, так как значение / ~(О) не определено; нельзя также просто просуммировать от 1 до гп, так как остаточные члены не дают убывающих степеней гп, если нижний предел равен 1. (Именно в этом состоит суть дела, и, прежде чем двигаться дальше, читатель должен убедиться в том, что он хорошо понял задачу.) Чтобы разрешить эту дилемму, можно положить по определению е ~(х) = (е к — 1)/х и / ~ — — у ~ (я/ь/2т); тогда / ~(0) = О и г ~(гп) нетрудно получить из 1 е<г<ь (1). Равенство (36) справедливо теперь и при й = -1, а оставшийся интеграл нам хорошо знаком (см, упр. 43): У-~(~) — — ~у = -3 — )пгп+)п2+О(е "'~т), Теперь у нас достаточна формул и фактов для того, чтобы вывести, наконец, ответ, который, как показано в упр.
44, имеет вид 1п = 1т1пгп.~. 1(у.11п2)гп — 1Яяпч.~. <э .ь г)(п ~/з), гл = и ~ 1, (Зу) Этим завершается анализ метода пузырька. Чтобы проанализировать метод обменной гюразрядной сортировки, нгюбходимо знать асимптотическое поведение при и -~ оо конечной суммы У„=~~ ) (-1)а ~~( —,) = ~~ (21(1-2 ")" -2У+и). (39) Ь>2 У>2 У>~ Если положить х = и/22, то член ряда зэлишется в виде 21(1 — 2 2)" — 21+и = — ~~1 — -) — 1+я При я < и' имеем .7= 1 — — ~ =ехр~п1п~1 — — ц~ =ехр(-х+я О(п )), 2 -1 (49) а это наводит на мысль о том, что следует аппроксимировать (39) рядом Т„= "~ (21е "~~ — 21 + и). (41) Чтобы подтвердить правомерность такой аппроксимации, рассмотрим разность б'„- Т„= Х„+ У„, где 21 -и!2~) (21( — -')" 1>2 22< $1- О(пе "~2 ) у>а 22<а~ О(п1окпе "') ]члены при к > и" ] ]поскольку О < 1-2 1 < е 2 ] (поскольку имеется О(1ойп) членов] 1„= ~ (2 (1-2-У)" 2те —.~ ') ]члены при к < и'] — ~е "~2~ и О(ц) 1>2 ]вследствие (40)] Определить его оказывается гораздо сложнее, чем решить другие задачи об асимптотическом поведении, с которыми мы сталкивались до сих пор; злементарные методы разложения в степенные ряды, формула суммирования Эйлера и т.
и. здесь бессильны. Следующий вывод был предложен Н. Г. де Брейном ( ч, С. де Вгш)п). Чтобы избавиться в формуле (38) от подавляющего влияния больших множи"жтей ф(-1)ь, начнем с того, что перепишем сумму в виде бесконечного ряда: Ниже будет показано, что эта последняя сумма есть О(1); значит, У вЂ” Т„= 0(1) (см. упр. 47).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
