Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 51
Текст из файла (страница 51)
Трибула (8. ТгуЬц)а) и Чжен Пинг (Р. Схеп), "недавно" опровергли его предположение и нашли значения 8(п) при и < 11. Вероятно, Трибула и Чжен Пинг независимо пришли к сортировке посредством вставок и слияния, о чем вскоре появилась публикация Гога, ЛоЬпэоп, АММ 66 (1959), 387-389. После открытия сортировки посредством вставок и слияния первым неизвестным значением функции 8(п) оставалось 8(12). Из табл. 1 видно, что число 12! довольно близко к 2»», поэтому существование 29-шаговой процедуры сортировки 12 элементов весьма маловероятно. Для решения этого вопроса Марком Уэлсом (Маг1» Ъе!1») был предпринят продолжительный вычислительный эксперимент (продолжавшийся на компьютере Машке П около 60 ч), который показал, что 8(12) = 30 [Ргос. 1ЛР Сопбге»э 65 2 (1965), 497-498].
Итак, процедура вставок и слияний оказывается оптимальной и при и = 12. «Более глубокий анализ, Чтобы более тщательно исследовать функцию Я(п), внимательно изучим диаграммы частичного упорядочения, подобные (5). Полученные после нескольких сравнений сведения можно представить в виде ориентированного графа. Этот граф в силу транзитивности отношения "<" не содержит циклов. Следовательно, его всегда можно изобразить таким образом, чтобы все дуги были ориентированы слева направо; поэтому удобнее удалить из диаграммы стрелки.
В результате диаграмма (5) преобразуется в (1)2 (1о), (па)2 (пааа)» (1 1 1 1000)» (10П010000)» (1оошопоооо), (1аошопоооаооо) (1опооо1оопооаоооа)» (пошоюпшоооооооо) (1оопоооа10001010100000000), (шоо1аоопоопш1оаооооаооо), (юшоопао1оюоопоопбоооаооооо)» (1оиоо1001юеешопоо101ооаоооооооо)» Паопооооошошошошоюпооооооаоооо), (1оопооаоошошошошо! опоооооооооооаооо), (ю1оооопошшошошопоопопаоооооооооооооо)» (1опо1опшашопоопаа10100п1оопооааоооооооооооо)» (попоооооо101оша01оапооооопо100оюо1оооооооооооооооо)» (юооошоааопопоошопш00100000101опо100оооооооооааооооо)» ш 1~ — 2! -ф — 4! = 5! = 6! = 7! = 8! = 91 = 10! ю 1И = 12! = 13! 14! = 15! = 16! = 17' м 18! — 1а! = 20! п с в (21) Пусть С вЂ” такой ориентированный граф; обозначим через Т(С) число перестановок, согласующихся с а, т.
е. число способов разметки вершин графа С целыми числами (1,2,..., и) так, чтобы число в вершине х было меньше числа в вершине у, если дуга х -+ у принадлежит С. Во| пример перестановки, согласуюшейся с (21): а = 1, Ь = 4, с = 2, И = 5, е = 3. Мы проанализировали функцию Т(С) для различных С в разделе 5.1.4, в котороч было отмечено, что Т(а) есть число вариантов топологической сортировки графа С. Пусть С -- граф нз п элементов, который можно получить после Ь сравнений; определим зф4ектпивносгпь графа С функцией и! 2ьТ(С) (22) (Эта идея принадлежит фрэнку Хвангу (Ггап)с Нжапя) и Шень Линю (Вйеп Ып).) Строга говоря, эффективность не есть функция лишь самого графа С вЂ” она зависит от того пути, которым мы пришли к С в процессе сортировки, однако для простоты закроем глаза на эту маленькую неточность.
Выполнив еще одно сравнение элементов 1 и у, получим два графа (С1 и Сз): один — для случая К, < К,, а другой -- для случая К, > К . Ясно, что т(с) = т(с ) + т(с ). Если Т(С1) > Т(Сэ), то имеем т(а) < 2т(а ), и( Е(а) Т(а) 2ь+'т(а,) 2т(а ) (23) Следовательно, каждое сравнение приводит к графу меныпей или равной эффективности; нельзя увеличить эффективность за счет дополнительных сравнений. Заметим, что если С совсем не содержит дуг, то к = 0 и Т(С) = и!, т. е. начальная эффективность равна 1.
Если же граф С представляет окончательный результат сортировки, то он выглядит, как отрезок прямой, и Т(С) = 1. Так, например, если нам нужно построить процедуру сортировки пяти элементов за семь нли менее сравнений, то необходимо получить линейный граф, эффективность которого ранна 5!/(2т х 1) = 120/128 = 15/1б, Отсюда следует, что все графы, возникающие в процессе сортировки, должны иметь эффективность > 1е; если бы появился какой-нибудь граф меньшей эффективности. то, по крайней мере, один из его потомков тоже имел бы л1еныпую эффективность и мы бы, в конце концов, пришли к линейному графу с эффективностью < Ц. В общем случае это рассуждение показывает, что все графы, соответствующие узлам дерева для некоторой процедуры сортировки п элементов, должны иметь эффективность > и!/2', где 1 — число уровней в дереве (не считая внешних узлов).
Это еше один способ доказательства неравенства о(п) > ~)5п1(, хотя такое рассуждение на самом деле не сильно отличается от приведенного вьшге, Граф (21) имеет эффективность 1, поскольку Т(С) = 15 и граф С был получен за три сравнения. Чтобы выяснить, какие вершины должны участвовать в следующем сравнении, можно построить матрицу сравнений а 5 с И е а О 15 10 15 11 Ь 0 0 5 15 7 С(С)= с 5 10 О 15 9 (24) с( О О 0 О 3 е 4 8 б 12 0 где С; есть Т(С~) для графа С~ Т (С)), полученного путем добавления дуги 1 -+ у в С.
Если мы, например, сравним К, с К„то 15 перестановок, согласующихся с С, распаду"гся на две группы: Сфс = 6, в которых Аа < Км н Ссе 9, в которых К, < К,. Последний граф имел бы эффективность 15/(2 х 9) у э < Ц, так что это сравнение ие может привести к процедуре сортировки нз семи шагов. Если мы хотим сохранить эффективность > —,, то следующим сравнением обязано быть 15 Кь:К Концепция эффективности особенно полезна при рассмотрении связных компонентов графов. Возьмем, например, граф 7 .г.
он состоит нз двух компонентов: а С' = а и С а В этих компонентах ни одна дуга не соединяет С' с С"; следовательно, он был образован путем нескольких сравнений вершин только С' и независимо нескольких сравнений вершин только С". В общем случае предположим, что граф С = С' 9 С" не содержит дуг, связывающих С' и С", где С' и С" имеют соответственно и' и и" вершин; легко видеть, что поскольку каждая перестановка, согласующаяся с С, получается в результате выбора и' элементов, которые считаются принадлежащими графу С', и последующего составления независимых перестановок, согласующихся с С' и С*'. Пусть внутри С' выполнено Й' сравнений, а внутри С" — соответственно йэ сравнений; получаем основной результат ( г+ я)~ м э~ ~(С) 2г ьь" Т(С) 2ь Т(С) 2ь Ту) ~(С )Е(С )~ (20) показьааюший, что между. эффективностью графа и эффективностью его компонентов существует простая связь.
Поэтому мы можем ограничить наше рассмотрение графами, имеющими только один компонент. Теперь предположим, что С' и Са — однокомпонентные графы и мы хотим связать их вместе, сравнив вершину х графа С' с вершиной р графа С". Нужно выяснить, насколько эффективньгм получится новый граф. Для этого нам понадобится функция„которую можно обозначить через (: .') (27) равная по определению числу перестановок, согласующихся с графом а1 аа ар (28) Таким образом, ('" < '„') есть произведение (™+") н вероятности того, что р-й наименьший элемент из множества т чисел меньше д-го наименьшего элемента из независимо выбранного множества и чисел, В упр.
17 показано, что функцию ( Р < а ) можно выразить через биномиальные коэффициенты двумя способами: (и — д+ т — «) (9 — 1+у) р<1< и д-1 (29) (Между прочим, алгебраически никоим образом не очевидно, что этн две суммы произведений бнномиальных коэффициентов должны быть равны.) Справедливы такие равенства; (~< Р) =( Р< ); (31) ("<'() =( р,<ч)+(р< ч,)+(р<.)(9= )(т+" 1).
(32) Рассмотрим два графа; аг Сд (33) Нетрудно показать с помощью простого перечисления, что Т(С') = 42 и Т(Са) = 5; так что если С вЂ” граф с 11 верпгинами, содержащий С' н Са в качестве своих компонентов, то по формуле (25) Т(С) = (ям) 42 5 = 69300. Такое число перестановок слишком внушительно, чтобы их можно было выписать и таким образом выяснить, в скольких из ннх яг < у для всех а и у.
Однако это вычисление менее чем за час можно проделать вручную следующим образом. Построим матрицы А(С') и А(С"), где Ага — число перестановок, согласующихся с С' (или С"), в которых х; (или 91) равно Й. Тогда число перестановок, согласующихся с С, в которых х! меньше у., есть сумма по всем р и о (1 < р < 7 и 1 < о < 4) произведений (1,р)-го элемента матрицы А(С'), (7 <') и (!',0)-ю элемента матрицы А(С").
Иначе говоря, нужно вычислить произведение матриц А(С ) ! . А(С )~, где Ещ —— (7 < 4). Оно равно 210 294 322 329 !26 238 3О1 Згб 70 175 265 315 35 Ыб 215 295 15 65 155 260 5 29 92 204 8 36 !20 48169 42042 66858 64031 < 22825 ьбО05 БЗ295 46475 4Ш69 42042 66858 6403! 22110 14850 54450 47190 5289 2442 27258 21131 22825 16005 53295 46475 5269 2442 27258 21131 21 !б 5 0 0 0 0 0 5 10 12 !О 5 0 21 16 5 0 0 0 0 0 0 12 18 12 0 0 0 О О О 5 16 21 0 51002!О 5 0 0 0 0 0 5 16 21 Таким образом, '"наилучший" способ соединить С' и С" — сравнить я! с уг! в 42042 случаях получим х! < у! и в 69300 — 42042 = 27258 случаях — х! > 92.
(В силу симметрии, по существу, к тем же результатам привели бы сравнения яэ с уг, яб с уз и х7 с 93.) Эффективность полученного графа для х! < уг равна 84084 т. е. она не особенно высока; следовательно, по-видимому, вообще не стоит ни в одном методе сортировки применять соединение С' с С"! Смысл этого примера— показать, что мы смогли принять такое решение, не производя непомерно больших вычислений. Этими идеями можно воспользоваться также для независимого подтверждения тою, что Я(12) = 30 (доказательство данного факта принадлежит Марку Уэлсу). Начав с графа, содержащего одну вершину, мы можем повторять попытки добавления сравнений к одному из наших графов С или к С' !9 С" (паре компонентов С' и С" ) с таким расчетом, чтобы оба полученных графа содержали 12 или менее вершин и обладали эффективностью > 12!/22" ю 0 89221.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
