С„ = п + 1 + (fc - l)(n - k)Ck-i

можно преобразовать в

(з)с„ - 2(" - )С„-, + - 2)с„-2 = 2(n - l)(n - 2) + 2(n - 2)С„-2.

29. В обш;ем случае рассмотрим рекуррентное соотношение

которое возникает, когда разделение управляется медианой 2t + 1 элементов. Патагая = En Cnz"", его можно преобразовать в (1 - zy+C+\z)l(2t + 2)! = 1/(1 - zf+ + С<"(г)/(<+1)!. Пусть /(ж) = C\l-x), тогдаp,{d}f{x) = {2t + 2y./x+\ где О - оператор x{d/dx) и pf(2;) = (< - - (2< + 2)+1. Обш;ее решение уравнения: (i9 - а)д{х) - х

имеет вид д{х) = 2;7(/3 - а) + Сх" при а ф /3 и д{х) = х1{1пх + С) при а = /З- Имеем pt{-t - 2) = О, так что обш;ее решение этого дифференциального уравнения таково:

C\z) = {2t + 2)! 1п(1 - z)/pt{-t - 2)(1 - zy+ + J2cj{l- z,

>=o

где Qo,..., Qf - корни уравнения pt{x) = 0, a константы a зависят от начальных значений Ct, , Сп- Удобное тождество

приводит к удивительно простому решению в замкнутом виде С„ p±lJil±L„ + 1) +

из которого легко выводится асимптотическая формула. (Главный член п In п/ {H2t+2 - Ht+i) выделил Ц. ван Эмден [см. М. Н. van Emden, САСМ 13 (1970), 563-567], используя теоретико-информационный подход. Действительно, предположим, что необходимо проанализировать произвольный процесс разделения, такой, что в левом подмассиве будет содержаться xN элементов с асимптотической вероятностью f{x) dx при iV -» оо, для О < X < 1. Ван Эмден доказал, что среднее число сравнений, необходимых для полной сортировки всего массива, имеет асимптотическое выражение Q~nlnn, где а = -1/{f{x) + /(1 - 2;))2; In х dx. Эта формула применима к обменной поразрядной сортировке, а также к быстрой сортировке и другим методам. См. также Н. Hurwitz, САСМ 14 (1971), 99-102.)

30. Решение 1 (представляет, скорее всего, историческую ценность). Каждый подмассив можно описывать четырьмя величинами {1,г,к,Х), где /иг - границы (как и ранее), к указывает число слов в ключах, о которых известно, что они равны во всем подмассиве, а X - нижняя граница (А;--1)-х слов в ключах. В предпатожении, что ключи неотрицательны, имеем вначале {1,г,к,Х) = (l,iV, 0,0). При разделении массива полагаем К равным {к + 1)-му слову проверяемого ключа Kq. Если К > X, то при разделении все ключи > К оказываются справа, а все ключи < К - слева (если смотреть каждый раз только на {к + 1)-е слово ключа). Соответственно разделенные подмассивы получают описания

{I, к, X) и {j,r,k,K). Но если К = X, то при разделении все ключи > К попадают вправо, а все ключи < К [фактически = К] - влево; разделенные подмассивы получают описания соответственно (/, j, А; + 1,0) и {j + l, г, к. К). В обоих случаях нельзя быть уверенным в том, что запись Rj заняла окончательное положение, поскольку мы не просмотрели (fe--2)-e слова. Для правильной работы с граничными условиями необходимо внести другие очевидные изменения. Добавив в описание пятый компонент, "верхняя граница", можно сделать этот метод симметричным относительно левой и правой частей массива.

Решение 2 [Bentley, Sedgewick, SODA 8 (1997), 360-369]. Пусть, как и в решении 1, К будет {к + 1)-ым словом в АГ, в подмассиве, описанном (/, г, к). Но далее используйте алгоритм из упр. 41 для разделения подмассива на три части, (/,г - 1,А;), {i,j,k + 1), {j + l,r,k), для случаев <К, =К, >К. Этот подход, который авторы назвали тиШкеу quicksort (быстрая сортировка по мультиключу), дает значительно лучшие результаты, чем решение 1, и является вполне достойным конкурентом самых быстрых методов сортировки символьных строк.

31. Выполните обычное разделение, и пусть Ri попадет в позицию Rs. Если я = т, то на этом можно закончить. Если s < т, воспользуйтесь тем же методом для нахождения (т - я)-го наименьшего элемента в правом подмассиве. Если же s > т, найдите т-й наименьший элемент в левом подмассиве. [САСМ 4 (1961), 321-322; 14 (1971), 39-45.]

В работе R. G. Dromey, Software Practice к. Experience 16 (1986), 981-986, показано, что понадобится меньше сравнений и перезаписей, если прекращать каждую фазу разделения, как только г или j достигнет позиции т.

32. Рекуррентное соотношение здесь следующее: Си = О и Спт =п+1+ {Апт + Впш)/п при п > 1, где

Апт = е Qn-s)(m-s) И Впт = Q»~l)m

l<s<m m<s<n

при 1 < m < П. Поскольку An+l){m+l) = Anrn + Спт и B(n+l)m = Впт + Cn т } можно

сначала найти формулу для Dn = {n+l)C„+i-)(rn+i) -пСпт, а затем сложить эти формулы и получить ответ 2((п--1)Я„-(п--2-т)Я„+1 „,-(т--1)Ят-1-п--)-з<5тп-<5т1-<5тпдт1. При п = 2т - 1 он примет вид 4т(Я2т-1 -Вт) +4т - 4Нт + (1 -Smi) = (4--41n2)m -41nm - 47 - f -Н 0(m-) » 3.39n. [См. D. E. Knuth, Proc. IFIP Congress (1971), 19-27.]

Другое решение является следствием теории, изложенной в разделе 6.2.2. Предположим, что ключи - это {1,2,..., п}, и пусть Xjk - число общих предков узлов j и к ъ дереве двоичного поиска, соответствующем быстрой сортировке. Тогда число сравнений, которые необходимо выполнить для реализации алгоритма из упр. 31, можно представить в виде YlJ=iXjm + Хшт - 2[узел m есть лист]. Вероятность того, что узел i является общим предком узлов j и к ъ случайном дереве двоичного поиска, есть 1/(шах(г, j, Л) - min{i,j,k) + 1). Среднее число сравнений получим, исходя из того, что EXjk = Hj + Hn+i-k + 1 - 2Hk-j+i при 1 < j < A: и Рг(узел m есть лист) = Рг(за m не следует т. ± 1 в случайной перестановке ) = -- Smi + g<5mn + 5<5mi<5mn. [См. R. Raman, SIGACT News 25,2 (June, 1994), 86-89.]

Анализ аналогичного алгоритма, в котором используется разбиение по методу медианы трех значений, приведен в работе Kirschenhofer, Prodinger, Martinez, Random Structures и Algoritlims 10 (1997), 143-156. Асимптотически более быстрый метод анализируется в упр. 5.3.3-24.

33. Действуйте, как на первой итерации поразрядной обменной сортировки, но вместо первого разряда числа используйте знаковый разряд.

34. В каждой итерации после обнаружения, по крайней мере, одного разряда, имеющего значение О, и одного разряда, имеющего значение 1, т. е. после первого же обмена, можно не

проверять условие i < j. Таким образом можно уменьшить время выполнения программы R примерно на 2С машинных циклов.

35. A = iV-l, В = (тшО, aveiVlgiV, max NlgN), С = NlgN, G = \N,K = LR = 0, S = \N - I, X = (min 0, ave \(N - 1), max - 1). В общем случае параметры А, С, G, К, L, R и S зависят от значений ключей в последовательности, но не от их начального расположения; начальное расположение ключей влияет только на параметры В и X.

36. (а) Еа)ф(-1)*+а, = E(;)a:j)(-l)*-a> = ЕОпа. = an. (b) (<5„о>; (-йщ); ((-1)"*<5„т); ((1-а)"); ((;)(-а)"(1-а)"-"*). (с) Запишем соотношение, которое требуется доказать, в виде Хп = Уп = cin + Zn- Тогда из п. (а) получим уп = an + Zn. Также 2~Е*>2()!/* = п, следовательно, уп удовлетворяет тому же рекуррентному соотношению, что и Хп- [Некоторое обобщение этого результата приводится в упр. 53 и 6.3-17. Оказывается, непосредственно доказать, что Хп = a„2"~V(2"~ - 1)> отнюдь непросто!]

37. (Em(2т)2") при произвольной ПОСЛедОВаТСЛЬНОСТИ констант со, С1, С2, .... [Из

этого ответа, хотя он и верен, не сразу видно, что (1/(п -- 1)) и (п - Sni) принадлежат к числу таких последовательностей! Последовательности вида (оп -I- йп) всегда являются двойственными по отношению к самим себе. Заметим, что в терминах производящих функций A{z) = Еапг"/п! имеем A{z) = eA{-z); следовательно, равенство А = А эквивалентно утверждению о том, что Л(г)е-/2 - четная функция.]

38. Итерация разделения, порождающая левый подмассив длиной s и правый подмассив длиной N - S, дает следующие вклады в суммарное время выполнения:

А = 1, B = t, C = N, K = Ssi, L = Sso, R = SsN, X = h,

где t - число таких ключей среди Ki,...,Ks, разряд b которых равен 1, а Л - это разряд 6 ключа A+i; если s = N, то h = О (см. (17)). Это приводит к таким рекуррентным уравнениям, как

-=2-" е (l)C;){t+B.+BN-s)

0<t<s<n

= \{N-1) + 2-()Bs, TfleN>2; Во = Вг = О

(см. упр. 23). Применив для решения этих уравнений метод, описанный в упр. 36, получим формулы An = Vn -Un + 1, Bn = {Un +N-1),Cn = Vn+ N, Kn = N/2, Ln = Rn = f (Fn -Un -N) +.1, Xn = {An - Ln). Ясно, что Gn = 0.

39. После каждой итерации быстрой сортировки, по крайней мере, один элемент попадает в свою окончательную позицию, но этого не происходит при обменной поразрядной сортировке (см. табл. 3).

40. Если переключаться на метод простых вставок всякий раз, как только на шаге R2 будет г - I < М, то проблема разрешится, если только не встретится более М равных элементов. Если последнее весьма вероятно, то всегда, когда на шаге R8 будет j < I или j = г, можно проверить условие Ki = - Кг.

41. В работе Lutz М. Wegner, IEEE Trans. С-34 (1985), 362-367, проанализировано несколько подходов, из которых описанный ниже нам представляется наиболее подходящим для использования на практике. Он несколько упрощен в работе Bentley, МсПгоу, Software Practice <fe Exp. 23 (1993), 1256-1258. Основная идея состоит в том, чтобы работать с массивом, разделенным на пять частей