Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 75
Текст из файла (страница 75)
Аналогичным образом получаем соотиошеняя Вл(г) = ~ ~ Ьгнлг" В,-1(г)Вл-,(г), г=! >=Е л Сл(г) = — ~ *л"'С,-1(г) Сл- (г), !У Ф Юл(г) = — з7'/2, (г)0л .(г), Е л Ел(г) = р) Е,-,(г)Ен- (г) г $ при Ж > М. Здесь Ьмя — вероятность того, что э и Х примут данные значения в последовательности длиной 5/, а именно Последнее выражение равно произведению трех сомножителей: числа перестановок множества (1,..., з — 1), числа перестановок множества (э+ 1,..., Н) и числа способов взаимной замены ! элементов нз одного подмассива и ! элементов из другого подмассива. Первый сомножитель есть произведение (1/Ж!) и (э — Ц1, второй сомножитель равен (5! — а)1, а третий равен (' )(, '). При 0 < !г С ЛХ получим Ви(Ъ) = Сн(з) = Вя(х) = 1, Р ( ) = П'= ((1+ (й — 1) )/5) В. ( ) г й =,((1+ а+ ".
+ ' ')/5). (Интересно проанализировать поведение этой производящей функции при большом йг; последовательность, аналогичная Сл(з), но г а~+', замененным на ам ~, как известно, сходится к распределению, отличному от нормального, что не позволяет проанализировать его полностью. (См. статью Р. Неппечп!п, М. Кейп!ег, П. 11оэ!ег, ВАХВО уяеогебса! 1п/огтабсз апд Аррйсайопз 23 (1989), 317-333; 23 (1989), 335-343; 26 (1991), 85-100.)] 23. При Ж > М получаем Ал = 1+ (2/Ж 'Х,езэ<л Аэ; Вл = Ее<э«л 5ми (! + В, ~ + Вл,) = (1/5Х) ),',((е-1)(!эХ вЂ” э)/(Н-1)+В,-~+Вл-,) = (!0-2)/6+(2/дг) ~ ейэ<лВэ ]см. упр. 22]; Рл = (2/УХ) 2 е«э<лРэ; Ян получается аналогично. При г! > 2М + 1 получаем Ял = (2/Ф) 4 о<э<и Яэ + (Н вЂ” 2М вЂ” 2)/К.
Каждое из этих рекуррентных соотношений имеет форму (20) при некоторой функпии /„. 24. Рекуррентное соотношение Ск = Н вЂ” 1+ (2/йг) 2„<л Сэ при Н > М имеет решение (!Ь'+1)(2Нл+~ -2Нм+э+1-4/(М+2)+2/(ХХ+1)). (Таким образом, мы могли бы сэкономить около 416/М сравнений. Но для каждого сравнения потребуется больше времени, если за ним последует анализ э и 11 В результате мы проиграем, если только потери при сравнении двух ключей не превысвт в -'М !п Ф раз потери от сравнения двух регистров. Многие теоретические выводы относительно сортировки не удалось реализовать на практике, посшшьку предлагаемые <усовершенствования" превращали быструю сортировку в существенно менее быструю!) 25.
(Многократно примените формулы (17), подставив а = 1.) А = 5Х вЂ” ЛХ, В = О, С = ( эа) — (и+'),Рм ВмВ=О. 26. Действительно, нет ничего хуже, чем сортировать 1 2 3 ... й! — М !9 !0-1 ... Ф-М+1. Часть этой вогледовательностн Х М-1 М вЂ” 2 ... 1 М АХ+1 ... Ф-1 почти так же плоха. Но это лишь чуть-чуть хуже, чем в упр. 25, посколысу при таком наборе получим Р=М вЂ” 1, Е= (и). 27. 12 231 8 6759 10 11 41614151320 1819172122 23; трсбует 546и.
Можно показать, что наилучшим при Н = 3(М + 1)2" — 1 будет случай, когда подмассивы прн каждом разбиении делятся пополам до тех пор, пока не достигнут размера ЗМ + 2. Затем нужно использовать деление на треть, чтобы избежать переполнения стека. Получим А = 3-2" -1, С = (й + э )(йг+ 1), Ю = 2э — 1, В = Р = Е = О. (Найти лучший случай для любого М и Ж вЂ” задача очень интересная, но и очень сложная.) 28. Рекуррентное соатношенне можно преобразовать в 29. В общем случае рассмотрим рекуррентное соотношение и 2 ~- (й — 1) (п — /с) 121+ 1/ которое возникает, когда разделение управляется медианой 2! + 1 элементов.
Полшвя С(л) = ~„"„С л", его можно преобразовать а (1 — л)'+'С!л'+'!(л)/(21+ 2)! = 1/(1 — л)'+ + С!0(л)/(!+1)(, Пусть /(х) = СО!(1-х); тогда рр(д)/(х) = (21+2)!/х'+~„где д — оператор х(!(/дх) н р!(х) = (! — х)'+' — (2! + 2)'+!. Общее рещение уравнения: (д — а)д(х) = хл имеет внд 9(х) = хл/(л — а) + Сх~ прн а .„а д н д(х) щ хя(!пх+ С) при а ы д. Имеем рс(-! — 2) = О, так что общее решение этога днфференпнального уравнения таково: Сн!(л) = (21+ 2)! 1п(1 — л)/р!(-! — 2)(1- л)'+ + ) с,(1 — л)"', где ае, ., а! — корни уравнения р!(х) = О, а константы с! зависят ат начальяых значений С!,..., Сл. Удобное тождество !и( — )ы~~1 (Н„е — Н )( )л", т>О, ейе приводит к удивительно простому решению в земкирщам виде С„= (н+ Ц+ —, ~ с (-а ) Н +! — Нс+! 1 :! Несет Ню+! нз которого легко выводится аснмптотнческая формула.
(Главный член и!пн/ (Нм+л— Н!е!) выделил М. ван Змден [см. М. Н. еап Епн!еп, САСМ 13 (1970), 563-567), используя теоретико-информационный подход. Действительно, предположим, что необходимо проанализировать произвольный процесс разделения, такой, что в левом подмассиве будет содержаться х7!! элементой с асимптотической вероятностью / /(х) дх прн Ж -+ аа, для 0 < х < 1, Ван Змден доказал, что среднее число сравнений, необходимых для полной сор! тировки всего массива, нмеет асимптотическое выражение а 'н (и и, где а = -1/) (/(х) + /(1 — х))х )и х де. Зта формула применима к обмеяной поразрядной сортировке, а также к быстрой сартнровке и другим методам.
См. также Н. Нпгвчсз, САСМ 14 (1971), 99-102.) 30. Рещение 1 (представляет, скорее всего, историческую ценность). Каждый подмасснв можно описывать четырьмя величинами (1, г, к, Х), где ! и г — граннць! (как н ранее), й уназывает число слов в ключах, о которых нзвестно, чта оня равны ва всем падмассиве, а Х вЂ” нижняя граница (я+1)-х слов в ключах. В предположении, чта ключн неотрнцательны, нмеем вначале (1, г, й, Х) = (1, Ф,О,О). При разделении массива полагаем К равным (й+ 1)-му слову проверяемого ключа Ке. Еслн К > Х, то при разделения все ключн > К оказываются справа, а все ключи < К вЂ” слева (еслн смотреть каждый раз только на (й + 1)-е слово ключа).
Соответственно разделенные подмасснвы получают описания (1, в'-1, и, Х) и (в', г,)в, К). Но если К = Х, то при разделении все ключи > К попадают вправо, а все ключи < К ]фактически = К] — влево; разделенные подмассивы получают описании соов ветственно (1, в к+ 1, 0) и (2+ 1, г к К). В обоик случаях нельзя быть уверенным в том, что запись Йв заняла окончательное положение, поскольку мы не просмотрели ((в+ 2)-е слова. Для правильной работы с граничными условиями необходимо внести другие очевидные изменения.
Добавив в описание пятый компонент, "верхняя граница", можно сделать этот метод симметричным относительно левой и правой частей массива. Решеиее 8 (Вепс!еу, Бебйешю)в, ЯООА 6 (1997), 360-369]. Пусть, как и в решении 1, К будет (к+ 1)-ым словом в К» в подмассиве, описанном (1, г, (г), Но далее используйте алгоритм из упр. 41 для разделения подмассива на три части, (1,в — 1,к), (в)у,й + 1), (в'+ 1,г,к), для случаев <К, =К, >К.
Этот подход, который авторы назвали ши(Вйеу 4ивсбвогв (быстрая сортировка по мультнключу), дает значнтелъно лучшие результаты, чем решение 1, н квляегся вполне достойным конкурентом самых быстрых методов сортировки символъных строк. 31. Выполните обычное разделение, и пусть Вл попадет в позицию Л . Если в = ш, то иа этом можно закончить. Если в < т, воспользуйтесь тем же методом для нахождения (пв — в)-го наименъшего элемента в правом подмассиве. Если же в > т, найдите т-й наименьший элемент в левом подмассиве. (САСМ 4 (1961), 321-322; 14 (1971), 39-45.] В работе К.
С. 11гошеу, Бойэвате Ргасйсе бв Ехрепелсе 16 (1986), 981 — 986, показано, что понадобится меньше сравнений и перезаписей, если прекращать каждую фазу разделении, как только в или у достигнет позиции т. 32. Рекуррептное соотношение здесь следующее: Сы = О и С„= и+ 1+ (А„+ В„„,)/и прил >1, где А = ~~ С1„„ц н Влт = ~~~ С( м, 16ю< т<вй» пРи 1 < гл < и. ПосколькУ А<„~вд е» = А, + Се и В;„+и = В + С „можно сначала найти формулу для В„= (и+ 1) Сшэц~,„+Ы -пС„,„, а затем сложить эти формулы и получить ответ 2((п+1)Н (и+2 пв)Н э1- ~ (ш+1)Жи+н+ ) Зб ви Зб~ 1 вб вбть Прн и = 2гл — 1 он примет вид 4гл(Нем в — Нм) + 4т — 4Н~ + -(1 — бмв) = (4+ 4!и 2)ш— 4 !впь — 47 — -' + О(гл ') = 3 39п.
(См. П. Е. Кпцсл, Ргос, 1Р)Р Сопбгвви (1971), 19-2Ц Другое решение является следствием теории, изложенной в разделе 6,2.2. Предположим, что ключи — это (1,2,..., и), и пусть Х ь — число общих предков узлов в' и (в в дереве двоичного поиска, соответствующем быстрой сортировке. Тогда число сравнений, которые необходимо выполнить для реализации алгоритма из упр. 31, можно представить в виде 2 ",Х, + Х вЂ” 2(узел гл есть лист]. Вероятность того, что узел в является общим предком узлов у и й в случайном дереве двоичного поиска, есть 1/(шах(в',у,л)— ппв(в,у',й) + 1).
Среднее число сравнений получим, исходя из того, что ЕХ в ж Н. + Н +, в+ 1 — 2Н» в ы при 1 < 1' < л и Рг(узел ш есть лист) = Рг(за пв не следует гл х 1 в случайной перестановке ) = в + ебтв + 1б~„+ вб„,~бпьв [См. К. Вешав, 81САСТ Меев 26, 2 (Лове, 1994), 86-89.] Анализ аналогичного алгоритма, в котором используется разбиение по методу меди»- ны трех значений, приведен в работе К1гзсйепЬо(ег, Ргоб)пбег, МагВпш, Иалдош Ввгисвнгви н А18огйлшз 1О (1997), 143-156. Асимптотически более быстрый метод анализируется в уцр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
