Время выполнения зависит от шести параметров, из которых лишь один зависит от исходных данных (остальные пять являются функциями только от N): Т = t, числа "внешних циклов"; А = t{t + 1)/2, числа просмотров, или "внутренних циклов"; В - числу обменов (переменному); С = числу сравнений; D - числу блоков последовательных сравнений; Е = числу неполных блоков. Если 7V = 2, то можно показать, что D = {t -2)N + t + 2и Е = 0. Для данных из табл. 1 Г = 4, А = 10, Б = 3+0+1+4+0+0+8-1-0+4+5 = 25, С = 63, D = 38, Е = О, так что общее время выполнения равно 1Ы+6Б + 10С+2£;+12Г+1 = 939и.

Панни показал, что в общем случае D = ei(iV+1) - 2(2 -1), Е= (з"") + (i+ «2 + • • • + er-i) - (ei - 1)(г - 1), если iV = 2 + • • + 2-.

13. Нет, так же, как и алгоритмы Q и R.

14. (а) Если р = 1, то при последнем слиянии выполняем (2" - 0) + (2" - 1) + (2" - 2) + (2-" -4) + • • • + (2- - 2*-2) = (t- 1)2*-Ч 1 сравнений; (Ь) Z( = X(-i + i(t- 1) + 2"* = =xo + Т,о<к<Д> + 2"*") = 5 (2) + 1 - 2"*- Следовательно, c(2*) = 2*-2(<2 -t + 4)-l.

15. (a) Рассмотрите число сравнений, таких, что i + d = N; затем примените индукцию по г. (Ь) Если Ь(п) - с(п+ 1), то имеем Ь{2п) = а(1) + + а(2п) = а(0) + а(1) + а(1) + • • • +

а{п - 1) + а(п) + z(l) + z(2) +----1- z(2n) = 2b(n) + у(2п) - a(n); аналогично Ь{2п + 1) =

2Ь{п) + у{2п + 1). (с) См. упр. 1.2.4-42. (d) Весьма трудоемкие вычисления выражения {z{N) + 2z{[N/2}) + •••)- a(N) с использованием таких формул, как

E2*(n-fc) =2"+ - п-2,

А:=0

приводят К результату

Ё2(";)=2--(" + 2)-1,

*:=0

ciN) = N[\[)+2ei-l)-r{ei-l)-l

16. Рассмотрим () путей на решетке из (0,0) в {п,п), как на рис. 11 и 18, и присвоим серии от до (г + вес f{i - j), если г > j, и f{j - г - 1) + 1, если i < j; здесь f{k) - число изменений разрядов Ьг / br+i в двоичном представлении к = (...626160)2-Если 7V = 2п, то общее число обменов в окончательном слиянии равно X]o<j<i<n(2/(J) +

l)Ci-j)C"n-i\ Седгевик показал, что в общем случае / эта сумма упрощается и

приводится к виду () + 2Еа:>1 (п-к) Yo<j<k fU) затем он использовал метод гамма-функции и получил асимптотическое выражение

где S{n) - периодическая функция Ig п с ограниченной амплитудой .0005. Следовательно, в среднем около 1/4 сравнений приведет к обмену при п оо. [SICOMP 7 (1978), 239-272; см. также Flajolet, Odlyzko, SIAM J. Discrete Math. 3 (1990), 238-239.]

17. Значение Kn+i проверяется при сортировке подмассива, для которого г = N и Ki - наибольший ключ. Ко проверяется на шаге Q9, когда минимум слева направо погружается до позиции Л] .

18. На шагах Q3 и Q4 до перехода к Q5 выполняется единственная замена г на j; процесс разделения подмассива Ri... Rr заканчивается при j = [(/-)-г)/2] на шаге Q7, т. е. подмассив разделяется по возможности точно пополам. (Количественно это выражается в том, что формулы (17) заменяются формулами А = 1, В = [{N-1)/2}, С - N + {Nmod 2); это, по существу, наилучший случай для алгоритма (см. также упр. 27, приведенное ниже), за исключением того, что В и С Если на шагах Q3 и Q4 заменить знаки "<" знаками "<", то алгоритм вообще не будет сортировать данные. Даже если предполагать, что в (13) стоят знаки "<", все равно наш алгоритм поменяет местами Ro с Ri, затем в третьей фазе разделения переместит исходную запись Ло в позицию Лг и т. д. Настоящая катастрофа!

19. Да, подмассивы можно обрабатывать в любом порядке. Но в очереди будет Q{N/ /s/log N) элементов, если каждая очередная итерация будет разбивать массив ровно пополам, в то время как стек гарантированно остается меньшим по объему (см. следующее упражнение).

20. тах(0, [lg(iV+2)/(M+2)J). (Самый плохой случай - это когда iV = 2*(М -)- 2) - 1 и все подмассивы разделяются точно пополам.)

21. На шаге Q6 точно t записей перемещается в область Rs+i Rn , поскольку В = t. Когда фаза разбиения завершается, то j - s. Следовательно, С - C = N+1-s есть количество вычитаний 1 из j. На шаге Q7 мы должны получить i = s + 1, если ключи различны, поскольку г == j влечет за собой Kj = К. Таким образом, С = s.

22. Указанное соотношение для An{z) легко вывести, поскольку As-i{z)An~s{z) - производящая функция для величины А после независимой сортировки случайных последовательностей длиной S - 1 и 7V - S. Аналогичным образом получаем соотношения

JV s

Bn{z) = Y YbstNZ*Bs-l{z)BN-siz), a = I f=0

Cn{z) =

5 = 1

1

при N > М. Здесь bstN - вероятность того, что sat примут данные значения в последовательности длиной 7V, а именно

Последнее выражение равно произведению трех сомножителей: числа перестановок множества {1,..., S - 1}, числа перестановок множества {s+ 1,..., N} и числа способов взаимной замены t элементов из одного подмассива и t элементов из другого подмассива. Первый сомножитель есть произведение (l/TV!) и (s - 1)!, второй сомножитель равен (7V - s)!, а третий равен При О < 7V < М получим Bjv(J) = Cn{z) = Sn{z) = 1,

Dn{z) = nLi((l + - и Eiz) = nLi((l + г + • • • + z-)/k).

[Интересно проанализировать поведение этой производящей функции при большом 7V; последовательность, аналогичная Cn{z), но с 2+, замененным на 2~, как известно, сходится к распределению, отличному от нормального, что не позволяет проанализировать его полностью. (См. статью Р. Hennequin, М. Regnier, U. Rosier, RAIRO Theoretical Informatics and Applications 23 (1989), 317-333; 23 (1989), 335-343; 25 (1991), 85-100.)]

23. При N > M получаем An = 1 + (2/7V) Eo<A:<jv Bn = Eo<t<.<jv >tN{t + B-i + Bn-s) = (1/7V) f(5-l)(N-5)/(7V-l)+B, i+Bjv ,) = (N-2)/6+(2/N) Eo<fc<iv5fc [см. упр. 22]; Dn = (2/7V) Eo<A:<iVjD*; En получается аналогично. При N > 2М + 1 получаем Sjv = (2/N) Eo<A:<jv k + {N - 2M - 2)/N. Каждое из этих рекуррентных соотношений имеет форму (20) при некоторой функции /„.

24. Рекуррентное соотношение Cn - N -\ + {2/N) Ylo<k<n "ри N > М имеет решение (+1)(2Ял+1-2Ям+2+1-4/(М+2)+2/(--1)). (Таким образом, мы могли бы сэкономить около iN/M сравнений. Но для каждого сравнения потребуется больше времени, если за ним последует анализ г и j. В результате мы проиграем, если только потери при сравнении двух ключей не превысят в -MlnN раз потери от сравнения двух регистров. Многие теоретические выводы относительно сортировки не удалось реализовать на практике, поскольку предлагаемые "усовершенствования" превращали быструю сортировку в существенно менее быструю!)

25. (Многократно примените формулы (17), подставив s = 1.) A = N - М, В = 0, С = {f)-r),D = E = S = 0.

26. Действительно, нет ничего хуже, чем сортировать

12 3 ... N-M N N-1 ... N-M+1.

Часть этой последовательности 7V М-1 М-2 ... 1 М М+1 ... N-1 почти так же плоха. Но это лишь чуть-чуть хуже, чем в упр. 25, поскольку при таком наборе получим i3 = M-l,£=().

27. 12 2 3 1 8 6 7 5 9 10 11 4 16 14 15 13 20 18 19 17 21 22 23; требует 546и. Можно показать, что наилучшим при N - 3{М + 1)2* - 1 будет случай, когда подмассивы при каждом разбиении делятся пополам до тех пор, пока не достигнут размера ЗМ + 2. Затем нужно использовать деление на треть, чтобы избежать переполнения стека. Получим А = 3-2* - 1, С = {к+ 1 )(7V + 1), 5 = 2* - 1, В = D = г; = 0. (Найти лучший случай для любого М и N - задача очень интересная, но и очень сложная.)