AOP_Tom3 (1021738), страница 177
Текст из файла (страница 177)
(САСЛЛ 4 (1961), 321-322; 14 (1971), 39-45.] В работе К. С Вгогиеу, Яойи аге Ргасбсе б< Ехрепепсе 16 (1986), 981-986, показано, что понадобится меньше сравнений и перезаписей, если прекращать каждую фазу разделения, как только !или Л достигнет позиции т. 32. Рекуррентное соотношение здесь следующее С~1 = 0 и С ж = и+1+ (А, + В„)/и при и > 1, где Аи» = ~ С! -л!!л — г) и В<» = ~' С1, 1!„„ <в<и 1«< при 1 < т < и. Поскольку А1„+18 ем —— А„м+ С„ж и В,„.г1! — — В, + С „можно сначала найти формулу для В„= (и+1)С1„ьп!,иеп — пС„, а затем сложить эги формулы и получить ответ 2((п+1) Н„-(и+2-т) Н„+1 — (т+1) Н,„+и+ 5) — -'бж „вЂ” -'бао — 1б„,„б При п = 2т — 1 оп примет вид 4гл(Нэ г — Н ) +4т — 4Н + з(1 — бч~) = (4+4!и2)т— 4!пт — 47 — д + О(т ') 3.39п.
(См. В. Е. КпиНь Ргос.!РЛР Солбгезэ (1971), 19-27.) Другое решение является следствием теории, изложенной в разделе 6 2.2. Предполо. жим, что ключи — это (1, 2,..., и), и пусть Х ь — число общих предков узлов Л и й в дереве двоичного поиска, соответствующем быстрой сортировке. Тогда число сравнений, которые необходимо выполнить для реализации алгоритма из упр 31, можно представить в виде 2 ",Х, + Хмж — 2(Узел т есть лист). ВеРоЯтность того, чта Узел ю ЯвлаетсЯ общим предком узлов Л' и !г в случайном дереве двоичного поиска, есть 1!'(шах(1,Л, !г)— гп!п(ьу',й) + 1). Среднее число сравнений получим, исходя из того, что ЕХгь = Н + Н„~1 ь + 1 — 2Нь <.1 при 1 < Л < й и Рг(узел гп есть лист) = Рг(за гл не следует тг х 1 в случайной перестановке ) = -' + -'б 1 + -'б~, + — 'б„1бы„.
(См. К. Катав, 31САСТ №кэ 25, 2 (Липе, 1994), 86-89.! Анализ аналогичного алгоритма, в котором используется разбиение по методу медианы трех значений, приведен в работе К!гэс!1епЬо!ег, Ргог!щбег, Мэг!!пех, КащЛощ Я!гас!игеэ и А!8ог!Йтз 10 (1997), 143-156. Асимптотически более быстрый метод анализируется в упр. 5.3.3.24. ЗЗ.
Действуйте, как на первой итерапии поразрядной обменной сортировки, но вместо первого разряда числа используйте знаковый разряд. 34. В каждой итерации после обнаружения, по крайней мере, одного разряда,имеюи!его значение О, и одного разряда, имеющего значение 1, т.
е. после первого же обмена, можно ие проверять условие с < 71 Таким образом можно уменьшить время выполнения программы В примерно на 2С машинных циклов. 35. А = !Ус — 1, В = (щсп О, аге -'сУс !8 Ж, тах -'сУг!8Х), С = У!8 !7, С = зсУс, К = Ь = В = О, В = 1дс — 1, Х = (щ!и О, аке —,'(сгс — 1), снах сгс — 1). В общем случае параметры А, С, С, К, Е, В и В зависят от значений ключей в последовательности, но не от их начального расположения; начальное расположение ключей влияет только на параметры В и Х. 36. (а) ~ (")(л)( — 1)ь 'са = 2 (")(л 1)( — 1) са.
= 2„(")бсоас — — а„. (Ь) (б а); (-б„с); (( 1)"'б ); К1 — а)"); ((,"„)( — а) (1 — а)" ы), (с) Запиваем соотношение, котороетребуется доказать, в вида х„= у„= а„+ х . Тогда из и. (а) получим р„= а + х„. Также 2 2 ьйз(„)рь = х„; следовательно, р„ удовлетворяет тому же рекуррентному соотнопсению, что и х„. [Некоторое обобщение этого результата приводится в упр. 53 и 6.3 — 17. Оказываетси, непосредствеенно доказать, что х„ = а 2" '/(2" ' — 1), отнюдь непросто!) 37. (2,„ с ( " )2 ") при ~роизвальной последовательности консзант се, сс, се, ....
(Из этого ответа, хотя он и верен, не сразу. видно, что (1/(и 4- 1)) и (и — б с) принадлежат к числу таких последовательностей! Последовательности вида (а„ + а ) всегда являются двойственными по отношению к самим себе. Заметим, что в терминах производящих функций А(х) = 2 а„х"/и! имеем А(х) = с*А( — х); следовательно, равенство А = А эквивалентно утверждению о том, что А(х)е-*Л -- четная функция.) 38. Итерация разделения, порождающая левый подмассив длиной в и правый подмассив длиной Ссс — в, дает следующие вклады в суммарное время выполнения: А=1, В=1, С=ссс, К=б,с, б=бр, В=б,н, Х=Ь, где 1 — число таких ключей среди Кс,...,К„разряд Ь которых равен 1, а Ь вЂ”.- это разряд Ь ключа К,ес; если в = !7, то Ь = О (см.
(17)) Это приводит к таким рекуррентным уравнениям,как Вя=2 ~ ( ) ( )(1+В,+Вч — ) о<с<с<л' = -(сгс — 1) + 2' я ~ ! 1 В„ где ссс > 2; Во = Вс = О 4 1 в) ,>г (см. упр. 23). Применив для решения этих уравнений метод, описанный в упр. Зб, получим формулы Ак = 1сн — Вк + 1, Вл = — (Ьск + дс — 1), Сн = рн + сус, Кл = Х/2, Ен = Вн = -', (Ил — Ьсн — сл7) +.1, Хл = с(Ан — Ен) Ясно, что Сн = О. 39.
После каждой итерации быстрой сортировки, по крайней мере, один элемент попадает в свою окончательную позицию, но этого не происходит при обменной поразрядной сортировке (см. табл. 3). 40. Если переключаться на метод простых вставок всякий раз, как только на шаге В2 будет г — ! < М, то проблема разрешится, если только не встретится более М равных элементов. Если последнее весьма вероятно, то всегда, когда на шаге ВЗ будет 7 < ! или / = г, можно проверить условие Кс = . = К„. 41. В работе Ьнсх М.
Жебост, 1ЕЕЕ Тгалв С-34 (1985), 362 — 367, проанализировано несколько подходов, из которых описанный ниже нам представляется наиболее подходящим лля использования на практике. Он несколько упрощен в работе Вепс!еу, МсПгоу, Войваге Ргвсйсе бс Ехр. 23 (1993), 1256.1258. Основная идея состоит в том, чтобы работать с массивом, разделенным на пять частей =К <К 'с >К =К а Ь с с! г до тех пор, пока средняя часть не станет пустой. Затеи нужно перебросить две крайние части в середину. В1. (Начальная установка.) Установить а л- Ь ь- 1, с ь- Ы е- г.
В2. (Увеличивать Ь до тех нор, пока не станет Кь > К.) Если 6 < с и Кь < К, увеличить Ь на 1 и повторить этот шаг. Если Ь < с н Кь = К, выполнить обмен Н +ь Нь, увеличить а и Ь на 1 и повторить этот шаг. ВЗ. (Уменьшать с до тех пор, пока не станет К, < К.) Если Ь < си К > К, уменьшить с на 1 и повторить этот шаг.
Если Ь < с и К, = К, выполнить обмен Н. еь Нв, уменьшить с и ь( на 1 и повторить этот шаг. В4. (Замена.] Если Ь < с, выполнить обмен Нь ь+ Нь, увеличить Ь на 1, уменьшить с на 1 и вернуться к шагу Р2. В5. !Очистка.) Выполнить обмен Нь,.ь еь Я, ь при 0 < Ь < пнп(а — 1,6 — а); также выполнить обмен Ньэь +ь Н ь при 0 < /с < пнв(ьЛ вЂ” с,г — ь!). Окончательно устаььовить ! ь- ! + 6 — а, у ь- г — с! л- с. 5 Совершенно очевидная моднфикшьия на шаге Р1 должна обеспечить эффективную обработку вырожденных случаев и обеспечить а < 6 и с < 4 до перехода к Р2.
Тогда исчезнет необходимость в проверках '"Ь < сь на шагах Р2 и РЗ (см. упр. 24). Более того, подобная замена позволит избежать обмена записи с самой собой. Одно ью приложений сортировки - — сбор зюпюей с равными ключами вместе. Таким образом, разделение на трн части зачастую более предпочтительно, чем разделение на две части, предусматриваемое алгоритмом Я. Операции обмена на шаге Р5 выполняются эффективно, поскольку все записи с ключами, равными К, к этому времени уже заняли свои окончательные позиции. Это упражнение придумано В.
Г. И. Фейеном (ЪЧ. Н. 3 геЦеп), который назвал его ипроблелюй голландского флага". "Задано множество объектов красного, белого и синего цветов, случайным образом разбросанных между тремя колонками. Нужно придумать способ взаимного обмена пар объектов таким образом, чтобы красные собрались в верхней части колонки, а синие — внизу, причем каждый объект должен просматриваться только один раз и разрешается использовать минимальное число дополнительных переменных для управления процессом'! (См.
Е. 1У. Р!1увсга, А Р!вс!р!!ло оГРгоугашш!лу (ргепь!се-На!1, 1976), СЬарьег 11~.) 42. Это особый случай теоремы Карпа (см. Н. М. Катр, ЗАСМ 41 (1994), 1136-1150, 32.8). Существенно более строгая асиьштотическая граница для хвоста распределения при быстрой сортировке была получена в работе С. 1. Н. МсР1апшй. В. В. Научать!, Х А!8оН16шв 21 (1996), 476 507. 43. При а -ь 0-1-, как следует нз упр. 1.2. 7-24, имеем 1 г у' (е г — 1)ьЛу+ ( у' 'е "ьЛу = Г(а) — 1/а = (Г(а+ 1) — Г(1))/а -ь Г'(1) = 7 р е ь 44. При й > 0 имеем гь(т) -'(2т)~ 'П~Г((6+1)/2) — бьо — 2',>е(-1)'Вь е ьь/ ((6+2/+ 1)/! (2т)1).
При Ь = — 1 вклады от (10 1(т) в (36) взаимно уничтожаются с подобными членами в разложении Н~ ы н имеем г ь(т) = Н ь+(1/ь(йтт) 2 ь>е( ь(!) — .-'(!п(2т)+ 7) — 2,>,( — 1)'Нзв/(2/)/! (2т)'. Поэтому вклад в И' ь члена Х'/! (33) получается с, „„, т~ 1-ь е р( 1~(2т)(1 1~(3тв+ !в(ГЗть)(1 !ь(4 зи1 !(2 !з/8 в) + О(т — Рз) = 1т!пт+ д(!п2+3)т —,~„ь(2кт+ ф+О(гл Рэ), 'Ллен -зХ' ' дает вклад * !Лмеетсв русский перевод: Дейкстра Э.
О. Дисявллкка лрогрвммвроввния — М.: Мкр, 1978, — Прим. иврвв, — -'2'ь>ь ехР(-1с/2т)(1 — ! /Зт )(1 — !/2т)(1+1/т) + О(пь Нс) = — -'/2хт+ -'. Член -'бьь дает вклад -'. И наконец, член -'(! — 1)Всйп с дает вклад —,'. т ' ~ ь>ь 1ехр( — 1/2т)+ 0(т-ь7с) = —,' + О(т-ь7с) 45. Рассуждение, использованное при выводе тождества (42), справедливо и для тождества (43), нужна только отбросить вычеты в точках х = -1 и г = О.
46. Действуя так же, как прн вычислении интеграла (45), получаем (в — 1)!/!и 2 + б,(п), где бь(сь) = — ~1 Я(Г(в — 2я«1с/!и2) ехр(2«п)с!бп)). 2 !и2 [Обратите внимание на то, что [Г(в+ В)[ = (Пес«<,()«~+1~))я/(!в!и)ьх1), где в > 0— целое, так чта можно найти верхнюю границу для функции б, (и).] 47. Сумма 2,>, е "«с (и/2')' на самом деле равна интегралу из упр. 46 при всех в > О. 48. Воспользовавшись промежуточным тождествам г — «асс-««» 1 — е = — / Г(х)х 'с!х, 2яь' / ь7с действуем так же, как описано в тексте, но теперь 1 — е ' выполняет роль е * — 1 + х; 1'„ь/(и+ 1) = ( — 1/2яь)1, ~ +' Г(в)п с(х/(2 * — 1) + О(п '), а интеграл равен 18п+ 7/!и 2 — ь — бо(п) в обозначениях упр. 46.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
