Теперь предположим, что G и О" - однокомпонентные графы и мы хотим связать их вместе, сравнив вершину х графа G с вершиной у графа G". Нужно выяснить, насколько эффективным получится новый граф. Для этого нам понадобится функция, которую можно обозначить через

\т п)

равная по определению числу перестановок, согласующихся с графом

01 02 Ор От

(27)

(28)

Ь\ 62 bq b„

Таким образом, (<) есть произведение С"") и вероятности того, что р-й наименьший элемент из множества т чисел меньше q-ro наименьшего элемента из независимо выбранного множества п чисел. В упр. 17 показано, что функцию (mn) можно выразить через биномиальные коэффициенты двумя способами:

( Р 1\ V + 1 + =)

п/ о<1<? т-р )\ р-1 )

= е гт.г)г,1\)- ™

p<j<m

(Между прочим, алгебраически никоим образом не очевидно, что эти две суммы произведений биномиальных коэффициентов должны быть равны.) Справедливы такие равенства:

(<) + (<П = (" + "); (30)

\т п) \п т) \ т )

\п т) \ т п )

= { <) + (< )+[р<т][, = п]Г+"-). (32) \т п) \т-\ п) \т n-lJ Л тп J

Рассмотрим два графа:

У1 уз

G= У<С , G"= / . (33)

У2 У4

-<11\

Нетрудно показать с помощью простого перечисления, что T{G) = 42 и T{G") = 5; так что если G - граф с 11 вершинами, содержащий G и G" в качестве своих компонентов, то по формуле (25) T{G) = {) • 42 • 5 = 69300. Такое число перестановок слишком внушительно, чтобы их можно было выписать и таким образом выяснить, в скольких из них Xi < yj для всех i и j. Однако это вычисление менее чем за час

можно проделать вручную следующим образом. Построим матрицы А{С) и A{G"), где Aik - число перестановок, согласующихся с G (или G"), в которых xt (или yt) равно fc. Тогда число перестановок, согласующихся с G, в которых Xi меньше yj, есть сумма по всем рид{1<р<7и1<д<4) произведений (г,р)-го элемента матрицы A{G), (7<4) и {j,q)-ro элемента матрицы A{G"). Иначе говоря, нужно вычислить произведение матриц A{G) • L А{С"У, где Lpq - {т<\)- Оно равно

/21 16 5 о О

О 5 10 12 10

21 16 5 О О

О О 12 18 12

О О О О 5 16 21 О 5 10 12 10 5 О V О О О О 5 16 21/

/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 3 О 0\ 2 2 0 1 10 2 2

\0 О 3 2/

/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/

Таким образом, "наилучший" способ соединить G и G" - сравнить xi с j/2; в 42042 случаях получим Xi < у2 и ъ 69300 - 42042 = 27258 случаях - xi > у2. (В силу симметрии, по существу, к тем же результатам привели бы сравнения хз с у2, хь с Уз и Хт с Уз.) Эффективность полученного графа для xi < у2 равна

69300 84084

E{G)E{G"),

т. е. она не особенно высока; следовательно, по-видимому, вообще не стоит ни в одном методе сортировки применять соединение G с G"\ Смысл этого примера - показать, что мы смогли принять такое решение, не производя непомерно больших вычислений.

Этими идеями можно воспользоваться также для независимого подтверждения того, что 5(12) = 30 (доказательство данного факта принадлежит Марку Уэлсу). Начав с графа, содержащего одну вершину, мы можем повторять попытки добавления сравнений к одному из наших графов G или к G ф G" (паре компонентов G и G") с таким расчетом, чтобы оба полученных графа содержали 12 или менее вершин и обладали эффективностью > 12!/2 и 0.89221. Всякий раз, когда это оказывается возможным, мы выбираем граф с меньшей эффективностью и добавляем его к нашему множеству, если только он не является изоморфным одному из уже включенных в множество графов. Если оба полученных графа имеют одинаковую эффективность, то произвольным образом выбирается один из них. Граф можно приравнять к двойственному ему графу (т. е. полученному в результате обращения отношения порядка) при рассмотрении вопроса о добавлении сравнений как к G ф dual(G"), так и к G (В G". Несколько графов, полученных таким способом, изображены на рис. 36, на котором приведены также значения их эффективности.

Прежде че.м этот процесс завершился, при помощи компьютера было построено ровно 1649 графов. Поскольку граф............не был получен,

.можно сделать вывод о том, что 5(12) > 29. Весьма правдоподобно, что и для доказательства неравенства 5(22) > 70 можно вьшолнить аналогичный эксперимент за вполне разумное время, поскольку 22!/2° » 0.952 - это чрезвычайно высокая эффективность для сортировки за 70 шагов. (Из 1 649 найденных графов с 12 или менее вершинами всего 91 имеет столь высокую эффективность.)

Промежуточные результаты дают веские основания предположить, что 5(13) = 33 и, следовательно, сортировка посредством вставок и слияния не оптимальна при

Gi • 1 G2 1 G3 < 1 G4 < Щ

re Oe < H G......Ц Gs --< Ц

Gi3 1 Gi4 * 1 GisH.! Gi6 7*64

Рйс. 36. Некоторые графы и значения их эффективности, полученные на начальной стадии длинного доказательства неравенства 5(12) > 29.

п = 13. Наверняка можно доказать, что 5(16) < F(16), поскольку F(16) - это как раз такое число сравнений, какое требуется, чтобы сначала рассортировать 10 элементов за 5(10) шагов, а затем посредством бинарных вставок вставить по одно.му остальные 6 элементов. Непременно должен существовать более хороший способ! Но в настоящее время вариант с наименьшим значением, в котором точно известно, что F{n) неоптимально, - это п = 47: после сортировки 5 и 42 элементов, где требуется F(5) + F(42) = 178 сравнений, мы можем слить результаты, на что потребуется еще 22 сравнения, используя метод, предложенный в работе J. Schulte Monting, Theoretical Сотр. Sci. 14 (1981), 19-37; этот результат превышает значение F(47) = 201. (В работе Glenn К. Manacher, JACM 26 (1979), 441-456, показано, что существует бесконечно много значений п, начиная с п = 189, для которых 5(п) < F{n).)

Среднее число сравнений. До сих пор мы рассматривали процедуры, наилучшие в том смысле, что они не плохи в наихудшем случае; мы искали "минимаксные" процедуры, минимизирующие максимальное число сравнений. Поищем теперь "мини-средние" процедуры, минимизирующие среднее число сравнений в предположении, что входные данные случайны, т. е. все перестановки равновероятны.

Рассмотрим еще раз изображенное на рис. 34 представление процедуры сортировки в виде дерева. Среднее число сравнений по всем перестановкам для этого дерева равно

2-ЬЗ + 34-3-ЬЗ-ь2 2

В общем случае среднее число сравнений для метода сортировки есть длина внешнего пути дерева, деленная на п\. (Напомним, что длина внешнего пути - это сумма всех расстояний от корня до каждого из внешних узлов; см. раздел 2.3.4.5.) Из анализа в разделе 2.3.4.5 следует, что минимальная длина внешнего пути достигается на таком бинарном дереве с N внешними узлами, у которого имеется 2 - N