38. Ej.n in)Pji-Pi)~4"2) = (2) EjPI; положив= F{j/M) - F{ij - 1)/M)hF{x) = f(x), эту сумма можно привести к произведению ()/М и f{x) dx, если только функция F подобрана достаточно хорошо. [Однако /(х) dx может оказаться слишком велико. Тонкости выбора, подходящего для всех ограниченных интегрируемых плотностей, приводятся в теореме 5.2.5Т. (Здесь имеется в виду интегрируемость по Риману. - Прим. ред.)]

39. Чтобы минимизировать величину АС/М + ВМ, нужно положить М = /ACjB, так что М - одно из целых, ближайшее (сверху или снизу) к этому значению. (В случае программы М можно было бы выбрать М пропорциональным Л.)

40. Асимптотические ряды для

Y ""(1 - aN)- = -N- + Y{N + к)-{1 - a/N)"

h>N к>0

можно получить, ограничившись значениями к до 0(7V"*), представив (1 - a/N) как произведение е""*-* и (1 - ka/2N + • • ) и использовав формулу суммирования Эйлера; теперь выражение начинается с членов eEi{a){l + a/2N) - (1 -I- a)/2N + 0(7V~). Следовательно, асимптотическое значение (15) есть 7V(lna +-у + Ei{a))/a + (1 - е~(1 + а))/2а + 0(7V"). [Коэффициент при N равен « 0.7966, 0.6596, 0.2880 соответственно для Q = 1, 2,10.] Обратите внимание на то, что, как показано в упр. 5.2.2-43, In а + 7--(а) =

j;ii-e-)t-4t.

41. Имеем ак = 0{р), поскольку из теоремы о простых числах следует, что количество простых чисел между и равно р*+У(/г + 1) - p/к + 0{р/к). Это значение положительно для всех достаточно больших к. Таким образом, сумма первых (2) элементов в соотношении (10) равна T.l<i<j<k>(Чj) = T,i<i<j<k 0{р). Отсюда получим

(b) Если (*-") < log < (2), имеем {к - 1) < 21og TV, поскольку р* = O(expcvTHlV).

Обратите внимание на то, что, поскольку р -> 1, базовая последовательность ai, 02, ... становится равной последовательности простых чисел и в теореме 1 граница снижается до 0(iV(logiV)(loglog7V)-3),

42. (а) [А. С. Yao, J. AJgoritiinjs 1 (1980), 14-50.] Можно показать, что каждая из (2) пар списков потребует p~/i~*7V* -I- 0{N/gh) инверсий на каждый подмассив {Ка,Ка+д, Ка+2д,.. •), 1 < О < р. Например, предположим, что /г = 12, р = 5, а = 1, и проанализируем инверсии, когда списки Кз < Кц < К27 < я Кг < Kis < К31 < пересекают подмассив [Кг, Кб, Ки,...). После первого прохода (Кз, Кг, К15, Kig, К27, К31,...) получается случайная 2-упорядоченная перестановка. Элементы Kj, которые нас особо заботят, имеют j = 1 (по модулю 5) и j = 3 или 7 (по модулю 12); следовательно, j = 51 или 31 (по модулю 60), а нам нужно вычислить среднее значение р(51,31), где

9{х, V) = y1 (t+sh > Ky+ghk] + [Ky+ghj > K+ghk]) + r{x, y),

3<k

r{x, y) = Y [min(:D,!,)+jhj > Km„(.y)+ghj] < N/gh .

Если jpj < p и g < p , TO получим

[Fi+ph-gh > Kk+qh+gh] < [Kj >АГа:] < [Kj+ph+gh > Kk+gh-gh] .

/г! А:" * / п! = \/KJ2n + 0{п ) = пренебрежимо малая величина.

V 1<А:<п / /

5. Можно считать, что г > 0. Пусть Ь, = (Ь; - г -I- l)[bi > г] - таблица инверсий после г - 1 проходов. Если bj > О, то элементу г предшествует bJ больших элементов, наибольший из которых всплывает, по крайней мере, до позиции bi + i (так как имеется г элементов < г).

[Kx+ghj > Ky+ghk] + [Ky+ghj > Kx+ghk]

< [Kx+ph+ghij + 1) > Ky+gH.+gh(k-l)] + [Ky+gh+ghU+l) >Kx+ph+gh(,k-l)]-

Отсюда следует, что g{x,y) < g{x + ph,y + qh) + 8N/gh. Аналогично найдем g{x,y) > g{x + ph, у + qh) - 8N/gh. Ho сумма g{x, y) no всем g парам (x, y), таким, что x mod h = b и у mod h = с для любого данного b ф с, к есть общее количество инверсий в случайной 2-упорядоченной перестановке 27У г элементов. Таким образом, как следует из упр. 14, среднее значение 9{х,у) равно д~л/тг~/Т28 {2N/h) + 0{N/gh).

(b) См. С. S. Janson, D, Е. Knuth, Random Structures and Algs. 10 (1997), 125-142. Если hug велики, имеем iP{h,g) = y/irh/128g + 0{g~-h) + 0{gh~).

43. Если К < Ki после шага D3, присвоить {Ki,..., Kj-k, Kj) {К, Ki,..., Kj-h); в противном случае выполнять шаги D4 и D5 до тех пор, пока КУК,. Здесь / = 1, если j = h + 1, а I I + 1 - h[l = h], если j увеличивается на 1. [См. И. W. Thimbieby, Software Practice к Exper. 19 (1989), 303-307.]

Другая идея повышения скорости выполнения программы состоит в том, чтобы при h > 1 выполнять сортировку только частично, не пытаясь продвинуть Kj влево далее позиции j-h [см. W. Dobosiewicz, Inf. Proc. Letters 11 (1980), 5-6], но, кажется, этот подход требует больше смещений.

44. (а) Да. Это очевидно в случае, когда тг оказывается на один шаг "выше" тг; в упр. 5.1.1-29 показано, что при таких условиях существует путь от тг к любой перестановке над ней. Этот путь образован операциями транспонирования соседних элементов.

(b) Да. Аналогично, если тг расположена "выше" тг, то тг расположена "ниже" тг".

(c) Нет; 2 1 3 не будет ни "выше; ни "ниже" 3 1 2, но 2 1 3 < 3 1 2.

[Частичное упорядочение тг < тг было впервые проанализировано Ч. Эресманом в контексте алгебраической топологии (С. Ehresmann, Annals of JVfatii. (2) 35 (1934), 396-443, §20). Многие математики называют его теперь порядком Брюа перестановок.]

РАЗДЕЛ 5.2.2

1. Нет, в ней на 2т + 1 инверсий меньше, где m > О - число элементов а*,, таких, что i < к < j я а, > Ок > aj. (Следовательно, любая обменная сортировка, в конце концов, приводит к упорядоченной перестановке.)

2. (а) 6. (Ь) [А. Cayiey, PhiJos. Mag. 34 (1849), 527-529.] Рассмотрим циклическое представление перестановки тт. Если поменять местами элементы одного и того оке цикла, то число циклов увеличится на 1; если поменять местами элементы разных циклов, то число циклов уменьшится на 1. (Это, по существу, содержание упр. 2.2.4-3.) Полностью рассортированная перестановка характеризуется тем, что она имеет п циклов. Следовательно, xch(7r) равно п минус число циклов перестановки тт. [Алгоритм 5.2.3S выполняет ровно хсЬ(7г) операций обмена записей; см. упр. 5.2.3-4.)

3. Да; относительное расположение равных элементов никогда не меняется.

4. Это вероятность того, что в таблице инверсий будет Ь] > тах(Ь2,..., Ьп). Вероятность равна

Кроме того, если элемент j - крайний справа среди всех элементов, которые предстоит обменять, то bj > О и после г-го прохода BOUND = bj + j - 1.

6. Решение 1. Элемент, наиболее удаленный вправо от своего конечного положения, перемещается нагодин шаг влево при каждом просмотре, кроме последнего. Решение 2 (более высокого уровня). Из упр. 5.1.1-8, ответ (f), aJ - г = 6; - Cj при 1 < г < п, где Cl С2 ... с„ - двойственная таблица инверсий. Если bj = max(6iЬ„), то Cj = 0.

7. (2(п + 1)(1 + Р(п) - Р(п + 1)) - Р(п) - P(nfY" = у/{2 - п/2)п + 0(1).

8. При г < А: + 2 имеется j + k - i + 1 способов выбора Ь,; при к + 2 <i <п - j + 2 имеется j - 1 /-1 способов; при г > п - j + 2 имеется п - i + 1 способов.

10. (а) Если i = 2k- 1, то из {к - 1, а, - к) в (к, а; - к). Если г = 2А:, то из (ai - к, к-1) в (а, - к, к). (Ь) Шаг a2k-i выше диагонали к < a2k-i - к Ф=>- aik-i > 2/. a2fc-i > а2к *=>• а2к < 2к - \ •<=>• а2к - к < к - 1 <=> шаг 02»; выше диагонали. Если поменять эти элементы местами, то поменяются местами горизонтальный и вертикальный шаги, (с) Шаг a2k+d будет, по крайней мере, на т единиц ниже диагонали Ф=>- к + т-1 > a2k+d - (к + т) + т a2k+d < 2к + т <=>• а2к > 2к + т а2к - к > к + тп <=> шаг 02*. (Если a2k+d < 2к + тпи а2к < 2к + тп, то имеется не менее {к + тп) + к элементов, меньших, чем 2А: + т, а это невозможно. Если a2k+d > 2к + тп и а2к >2к + тп, то один из знаков ">" должен быть знаком "> "; но невозможно поместить все элементы < 2к + тп в .менее чем (А; + т) + А: позиций. Следовательно, a2fc+2m-i < «2* тогда и только тогда, когда а2к+2т-} <2к + тп, т. е. когда 2к + тп < ог*. Довольно неожиданный результат!)

11. 16 10 13 5 14 6 9 2 15 8 11 3 12 4 7 1 (61 обмен). Ответ получается в результате анализа решеточной диаграммы. Ситуация усложняется, если 7V велико; в общем случае множество {К2, К4,- } должно быть таким: {1, 2,..., М - 1, М, М + 2, М + 4,..., 2 [7V/2J - М}; и его перестановка до.пжиа максимизировать число обменов для [N/2\ элементов. Здесь М = [273], где к максимизирует A;[7V/2J - ((ЗА: - 2)2*- + (-1)*). Суммарное максимальное число операций обмена записей равно произведению 1 - 2 Ig Ig N/ Ig N + 0(1/ log N) и числа сравнений [R. Sedgewick, SICOMP 7 (1978), 239-272].

12. В следующей программе, написанной В. Панни (W. Раппу), команда AND не используется - для этого шаг М4 выполняется при i = г + 2кр + s, к>ОиО<8<р. Здесь ТТ = 2", р = rll, г = г12, i = г13, i + d-N = iUiip-l-s = rI5; полагается, что N > 2.

Ml. Инициализация р. р 2*~. М2. Инициализаиия а. г. d. q2-\ г <- 0. г14 *г- d.

МЗ. Цикл по i. г <- г. г14 <- г -I- d - N. S <-0.

М4. Сравнение/обмен i?i4-i -.Ri-dA-i Переход, если Ki+i < Ki+d+i-

Ri+l <-> Ri+d+l-

Переход, если s = р - 1. s s + 1. i <- г -(-1.