AOP_Tom3 (1021738), страница 3
Текст из файла (страница 3)
В общем случае это рассуждение показывает, что все графы, соответствующие узлам дерева для некоторой процедуры сортировки и элементов, должны иметь эффективность > о!/2', где 1 — число уровней в дереве (не с п1тая внешних узлов). Это еще один способ доказательства неравенства Б(п) > (15п!), хотя такое рассуждение иа самом деле не сильно отличается от приведенного выше. Граф 121) имеет эффективность 1, поскольку Т(с) = 15 и граф С был получен за три сравнения. Чтобы выяснить, какие вершины должны участвовать в следующем сравнении, можно построить матрицу сравнений а 5 с Н е а 0 15 10 15 11 Ь 0 0 5 15 7 С(С)= с 5 10 0 15 9 (24) И 0 0 0 0 3 е 4 8 6 12 0 где СО есть Т(сь) для графа Сь Т (С1), полученного путем добавления дуги 1 -+ у в С.
Если мы, например, сравним К, с К„то 15 перестановок, согласующихся с С, распадутся на две группы: С„= 6, в которых К, < К„и С„= 9, в которых К, < К,. Последний граф имел бы эффективность 15/(2 х 9) =. ь < Ц, так что это сравнение не может привести к процедуре сортировки из семи шагов.
Если мы хотим сохранить эффективность > —,в, то следующим сравнением обязано быть 15 Кь Ке. Концепция эффективности особенно полезна при рассмотрении связных компонентов графов. Возьмем, например, граф с / он состоит из двух компонентов; а Ь С'= l и С" = с В этих компонентах ни одна дуга не соединяет С' с С"; следовательно, он был образован путем нескольких сравнений вершин только С' и независимо нескольких сравнений вершин только С".
В общем глучае предположим, что граф С = С' ~З С" не содержит дуг, связывающих С' н С", где С' и С" имеют соответственно тй и и" вершин; легко видеть, что т(С) = +, Т1С') Т~Св), (25) поскольку каждая перестановка, согласующаяся с С, получается и результате выбора и' элементов, которые считаются принадлежащими графу С', и последующего составления независимых перестановок, согласующихся с С' н С". Пусть внутри С' выполнено Й' сравнений, а внутри Св — соответственно )с" сравнений; получаем основной результат (и' + и")! и'! и"! 2ь" ь" Т(с) 2ь'Т(С') 2""Т(с') показывающий, что между эффективностью графа и эффективностью его компонентов существует простая связь. Поэтому мы можем ограничить наше рассмотрение графами, имеющими только один компонент.
Теперь предположим, что С' и С" — однокомпонентные графы и мы хотим связать их вмегте, сравнив вершину х графа С' с вершиной у графа С". Нужно выяснить, насколько эффективным получится новый граф. Для этого нам понадобится функция, которую можно обозначить через (Р 4) (27) равная по определению числу перестановок, согласующихся с графом аг аг (28) Ьг Ь Ьп Таким обРазом, ( г < «) есть пРоизведение ("'г,,") и веРоЯтности того, что Р-й наименьший элемент из множества т чисел меньше 9-го наименыпего элемента из независимо выбранного множества и чисел.
В упр. 17 показано, что функцию (,"„< «) можно выразить через биномнвльные коэффициенты двумя способами: (;и .')= К(' "'", ')(',"") о<в<« (29) (Между прочим, алгебранчески никоим образом не очевидно, что эти две суммы произведений биномиальных коэффициентов должны бьить равны.) Справедливы такие равенства: (30) ( и р ) (т+1 — р и+1 — д) (" < ~) = ( Р < ) + (Р < ~ ) +(Р<шП4=и)(,„) (31) (32) Рассмотрим два графа: 'Л Си (ЗЗ) Нетрудно показать с помощью простого перечисления, что Т(С') = 42 и Т(С") = 5; так что если С вЂ” — граф с 11 вершинами, содержащий С' и С" в качестве своих компонентов, то по формуле (25) Т(С) = (~4) 42 5 = 69300. Такое число перестановок слишком внушительно, чтобы их можно было выписать и таким образом выяснить, в скольких из них х«< р для всех г и ~. Однако это вычисление менее чем за час можно проделать вручную следующим образом.
Построим матрицы .4(С') и .4(С"), где Ам -- число перестановок, согласующихся с С' (или С"), в которых х! (или рл) равно lс. Тогда число перестановок, согласующихся с С, в которых х, меньше у, есть сумма по всем р и О (1 < р < 7 и 1 < О < 4) произведений (1,р)-го элемента матрицы А(С'), (~~<~) и (2,0)-го элемента матрицы А(С"). Иначе говоря, нужно вычислить произведение матриц А(С') . 1.. А(С")т, где 7„4 = ("<4). Оно равно 210 294 322 329 126 238 301 325 70 175 265 315 35 115 215 295 15 65 155 260 5 29 92 204 1 8 36 120 2! 16 5 0 О О 0 0 5 10 12 10 5 0 21 16 5 0 0 О 0 0 0 12 18 12 О 0 0 0 0 О 5 !6 21 0 5 10 12 10 5 О О 0 0 0 5 16 21 48169 42042 66858 64031 < 22825 16005 53295 46475 48169 42042 66858 64031 22110 14850 54450 47190 5269 2442 27258 21131 22825 16005 53295 46475 5269 2442 27258 21131 Таким образом, "наилучший" способ соединить С' и С" — сравнить х! с у21 в 42042 случаях получим х! < 92 и в 69300 — 42042 = 27258 случаях — х! > 92.
(В силу симметрии, по существу, к тем же результатам привели бы сравнения хэ с у2, хб с 93 и хт с 03.) Эффективность полученного графа для х! < 92 равна Е(С') Е(С" ), т. е. она не особенно высока; следовательно, по-видимому, вообще не стоит ни в одном методе сортировки применять соединение С' с С"! Смысл этого примера— показать, что мы смогли принять такое решение, не производя непомерно больших вычислений.
Этими идеями можно воспользоваться также для независимого подтверждения того, что 5(12) = 30 (доказательство данного факта принадлежит Марку Уэлсу). Начав с графа, содержащего одну вершину, мы можем повторять попытки добавления сравнений к одному. из наших графов С илн к С' ш С" (паре компонентов С' и С") с таким расчетом, чтобы оба полученных графа содержали 12 или менее вершин и обладали эффективностью > 12!7220 — 0.89221.
Всякий раз, когда это оказывается возможным, мы выбираем граф с меньшей эффективностью и добавляем его к нашему множеству, если только он не является изоморфным одному из уже включенных в множество графов. Если оба полученных графа имеют одинаковую эффективность, то произвольным образом выбирается один из них. Граф можно приравнять к двойственному ему графу (т. е. полученному в результате обращения отношения порядка) при рассмотрении вопроса о добавлении сравнений как к С' гьз 41па1(Сл), так и к С' Ы С". Несколько графов, полученных таким способом, изображены на рис. 36, на котором приведены также значения их эффективности.
Прежде чем этот процесс завершился, при помощи компьютера было построено ровно 1649 графов. Поскольку граф не был получен, можно сделать вывод о том, что 5(12) > 29. Весьма правдоподобно, что и для доказательства неравенства 5(22) > 70 можно выполнить аналогичный эксперимент за вполне разумное время, поскольку 22!/270 а 0.952 — — зто чрезвычайно высокая эффективность для сортировки за 70 шагов.
(Из 1 649 найденных графов с 12 или менее вершинами всего 91 имеет столь высокую эффективность.) Промежуточные результаты дак1т веские основания предположить, что о'(13) = 33 и, следовательно, сортировка посредством вставок и слияния не оптимальна при С4 С, К С1 ° 1 Ст а-~-~-е-е — Сб 16 16 16 16 6 ~Э~ ~16 Сб ~к~~ 116 16 Я збз С11 зы — С„ С>з 64~4-~~~> ° 1 С!4 $~ 1 С16 ~~ ~~° 1 С16 ~~~~~в 64 »1 З16 зм "фб С»4 ~~~ в 64 Сзз ~Я б 16 Рнс.
36. Некоторые графы и значения их эффективности, полученные на начальной стадии длинного доказательства неравенства 5(12) > 29. и = 13. Наверняка можно доказать, что 5(16) < Г(16), поскольку Г(16) — это как раз такое 1исло сравнений, какое требуется, чтобы сначала рассортировать 10 элементов за о (10) шагов, а затем посредством бинарных вставок вставить по одному остальные 6 элементов.
Непременно должен существовать более хороший способ! Но в настоящее время вариант с наименьшим значением, в котором точно известно, что г'(и) иеоптимально, — это п1 = 47: погле сортировки 5 и 42 элементов, где требуется Р(5) + г'(42) = 178 сравнений, мы можем слить результаты, на что потребуется еще 22 сравнения, используя метод, предложенный в работе Л. Вейн)ге Мбпсзпа, Тйеоге1- 1са! Со>пр. Бш. 14 (1961), 19" 37; этот результат превышает значение Р(47) = 201. (В работе П1епп К.
МапасЬег,,УАСМ 26 (1979), 441-456, показано, что существует бесконечно много значений п, начиная с и = 189, для которых Я(п) < г'(и).) 2 + 3 + 3 + 3 + 3 + 2 6 з В общем случае среднее число сравнений для метода сортировки есть длина виешпезо пути дерева, деленная на и.'. (Напол»ним, что длина внешнего пути -. это сумма всех расстояний от корня да каждого из внешних узлов; см. раздел 2.3.4.5.) Из анализа в разделе 2.3.4.5 следует, что минимальная длина внешнего пути достигается на таком бинарном дереве с 111 внешними узлами, у которого имеется 2» — 111 Среднее число сравнений. До сих пор мы рассматривали процедуры, наилучшие в том смысле, что они не плохи в наихудшем случае; мы искали 'минимаксные" процедуры, минимизирующие максимальное число сравнений.
Поищем теперь "минн- средние" процедуры, минимизирующие среднее число сравнений в предположении, что входные данные случайны, т. е. все перестановки равновероятны. Рассмотрим еще раз изображенное на рнс. 34 представление процедуры сортировки в виде дерева. Среднее число сравнений по всем перестановкам для этого дерева равно 01 .'ф,~~.э." ь'вф О.О О ~ > З 0.3 0.4 ОЛ 0 0 0.7 0.8 0.9 1.0 О.О Рнс. ЗЧ. Функция 1+ д — 2~. внешних узлов на уровне 9 — 1 и 2А> — 2" на уровне о, где д = (!8А>).
(Корень находится на нулевом уровне.) Таким образом, миннма |ьная длина внешнего пути равна (о — 1)(2' — А>) + О(2Х вЂ” 2') = (д+ 1) А7 — 2'. (34) Имеется еще один интересный способ охарактеризовать минимальную длину пути: расширенное бинарное дерево имеет минимальную длину внешнего пути тогда и только тогда, когда существует такое числа 1, что все внешние, узлы находятся на уровнях ! и ! + 1 (см.
упр. 20). Если положить О = !8А>+ 9, где О < В < 1, то формула минимальной длины внешнего пути примет вид >17(!8А>+1ч д 29) (35) График функции 1+ С вЂ” 29 изображен на рис. 37; при 0 < д < 1 она принимает положительные, но очень малые значения, не превыша>ощие 1 — (1+ 1п!и 2)/!п2 = О 08607 13320 55934+. (36) Таким образом, минимальная возможная средняя длина пути, которая получается в результате деления (35) на А>, нг может быть меньше !8 М и болыпе 18!>'+ 0.0861.
(Этот результат впервые получил Э. Глисон (А. С!еаэоп) в неопубликованной заметке 1956 года.) Если теперь положим А> = т>!,. то получим нижнюю оценку среднего числа сравнений по всем схемам сортировки. Оценка аснмптотически приближается к !8п!+ 0(1) = и !8п — и/1п 2+ О(!Ойп). (37) п=1 2 3 4 5 6 7 8 Нижняя граница (34) = О 2 16 112 832 6896 62368 619904 и! г (7>) = 0 2 16 112 832 6912 62784 623232 Итак, сортировка посредством вставок и слиянии оптимальна в обоих смыслах при т> < 5, однако при п = С такой метод в среднем требует 6912/720 = 9.6 сравнений вместо возможных согласно нижней оценке 6896/720 = 9.577777 . сравнений. Немного поразмыслив, нетрудно понять, почему это так: некоторые "удачные" перестановки шести элементов сортируются методом вставок и слияний всего за восемь сравнений, н тогда дерево сравнений имеет внешние узлы на трех, а не на двух уровнях. Изза этого увеличивается суммарная длина пути. В упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
