16. [НМ42] Найдите значение асимптотического выражения для среднего числа операций обмена, когда алгоритм Бэтчера применяется к случайной перестановке Л различных элементов, полагая, что Л есть степень двойки.

► 17. [20] Где в алгоритме Q используется тот факт, что Ко и Kn+i имеют значения, постулированные неравенствами (13)?

► 18. [20] Объясните, как работает алгоритм Q в случае, когда все ключи в исходном массиве равны. Что произойдет, если на шагах Q3 и Q5 заменить знаки "<" знаками "<"?

19. [15] Будет ли алгоритм Q по-прежнему работать правильно, если вместо стека (последним пришел - первым вышел) воспользоваться очередью (первым пришел - первым вышел)?

20. [М20] Выразите наибольшее число элементов, которые могут одновременно оказаться в стеке во время работы алгоритма Q, в виде функции от М и Л.

21. [20] Объясните, почему для фазы разделения в алгоритме Q требуется именно столько сравнений и пересылок, сколько определено в (17).

22. [М25] Пусть pkN - вероятность того, что величина А в (16) будет равна к, если алгоритм Q применяется к случайной перестановке множества {1,2,..., N}, и пусть An{z) = YjkPNz - соответствующая производящая функция. Докажите, что An{z) = \ при N < М, а An{z) = z{Y.i As-i{z)An-s{z))/N при N > М. Найдите аналогичные рекуррентные соотношения, определяющие другие распределения вероятностей Bn(z), Cn(z), Dn{.z), En{z), Sn{z).

23. [M23] Пусть An, Bn, Dn, En, Sn - средние значения соответствующих величин в (16) при сортировке случайной перестановки множества {1,2,... ,N}. Найдите для этих величин рекуррентные соотношения, аналогичные (18), затем найдите решения этих соотношений и получите формулы (25).

24. [М21 ] Очевидно, в алгорит.ме Q выполняется несколько больше сравнений, чем необходимо, потому что на шаге Q3 может получиться i = j, а на шаге Q5 - даже г > j. Сколько сравнений Cn выполнялось бы в среднем, если бы исключались все сравнения при i > j?

25. [М20] Чему равны точные значения величин А, В, С, D, Е я S для программы Q, когда исходные ключи представляют собой упорядоченный набор чисел 1 2 ... Л в предположении, что N > М.

► 26. [М24 ] Постройте исходную последовательность, при которой программа Q работала бы еще медленнее, чем в упр. 25. (Попытайтесь найти по-настоящему отвратительный случай.)

27. [М28] (Р. Седгевик (R. Sedgewick).) Рассмотрите наилучший случай для алгоритма Q, Найдите перестановку множества {1,2,..., 23}, которая требует меньше всего времени для сортировки при N = 23 и М = 3.

28. [М26] Найдите рекуррентное соотношение, аналогичное (20), которому удовлетворяет среднее число сравнений в алгоритме Q, модифицированном Синглтоном (т. е. когда в качестве s выбирается не s = Ki, а медиана из {Ki, Ki(n+i)/2j, Kn})- Не обращайте внимания на сравнения, которые необходимы при вычислении медианы s-

29. [НМ4О] Найдите значение асимптотического выражения для числа сравнений в алгоритме Синглтона "медиана из трех" (это упражнение является продолжением упр. 28).

► 30. [25] (П. Шеклтон (Р. Shackleton).) При сортировке ключей длиной несколько машинных слов работа многих алгоритмов все более замедляется по мере упорядочения массива, поскольку для определения правильного лексикографического порядка равных или почти равных ключей необходимо сравнить несколько пар слов (см. упр. 5-5). В массивах, которые встречаются на практике, часто содержатся почти равные ключи, и это явление может заметно отразиться на времени сортировки.

Объясните, как можно усовершенствовать алгоритм Q, чтобы избежать этого затруднения. В подмассиве, о котором известно, что старшие к слов во всех ключах содержат постоянные значения, следует проверять лишь (к + 1)-е слова ключей.

► 31. [20] (Ч. Э. Р. Хоар (С. А. R. Ноаге).) Предположим, что необходимо не рассортировать массив, а лишь определить т-й наименьший по величине элемент из заданного множества п элементов. Покажите, что алгоритм быстрой сортировки можно приспособить для этой цели, сократив значительную часть вычислений, которые используются для полной сортировки.

32. [М40] Найдите простое выражение в замкнутом виде для С„т - среднего числа сравнений ключей, необходимых для поиска т-го наименьшего из п элементов по методу быстрого поиска (см. упр. 31). (Для простоты можете положить М = 1; т. е. предполагается не использовать специальную методику обработки коротких подмассивов.) Каково асимптотическое поведение параметра C(2m-i)m - среднего числа сравнений, необходимых для нахождения медианы из 2т - 1 элементов методом Хоара?

► 33. [15] Разработайте алгоритм переразмещения чисел в некоторой заданной таблице таким образом, чтобы все отрицательные значения предшествовали положительным. Элементы полностью сортировать не нужно: достаточно просто отделить отрицательные числа от положительных. Алгоритм должен быть построен таким образом, чтобы минимизировалось количество операций обмена записей в памяти.

34. [20] Как можно ускорить циклы проверки разрядов при обменной поразрядной сортировке (шаги от R3 до R6)?

35. [М23] Проанализируйте статистические характеристики А, В, С, G, К, L, R, S и X, которые получаются при обменной поразрядной сортировке исходных данных наподобие (i).

36. [М27] Для любой данной последовательности чисел {а„) = ao,ai,a2,.. определите ее биномиальное преобразование (an) = йо, 0,1,0,2,... с помощью правила

a) Докажите, что (а„) = (а„).

b) Найдите биномиальные преобразования последовательностей (1), (п) и (()) при фиксированном т, (а") - при фиксированном а, (()а") - при фиксированных а и т.

c) Предположим, что последовательность (х„) удовлетворяет соотношению

х„ = а„-1-2-" Xfc прип>2; хо = xi = ао = ai = 0.

к>2

Докажите, что решением этого рекуррентного соотношения будет

2*-1 л. 2F-

к>2 к>2

37. [М28] Определите все такие последовательности {а„), что (а„) = (а„) в смысле упр. 36.

► 38. [МЗО] Найдите An, Bn, Cn, Gn, Kn, Ln, Rn h Xn - средние значения величин в (29) в случае, когда поразрядной сортировке подвергаются исходные данные наподобие (ii). Выразите ответы через N и функции

--ес). V. - е с) Ш

к>2 к>2

[Указание. См. упр. 36.]

-e(:)<-)is=«.+e(:)(-)h-

39. [20] Результаты (30) показывают, что поразрядная обменная сортировка, примененная к случайным входным данным, требует около 1.44iV итераций. Докажите, что для быстрой сортировки никогда не требуется более N итераций, и объясните, почему при обменной поразрядной сортировке часто необходимо более N итераций.

40. [21 ] Объясните, как нужно изменить алгоритм R, чтобы он работал достаточно эффективно и в том случае, когда в сортируемых массивах содержится много равных ключей.

► 41. [30] Разработайте такой способ обмена записей Ri...Rr, который обеспечивает их разбиение на три блока: (i) Kk < К при 1 < А; < г; (ii) Kk = К для г < к < j; (iii) Kk > К для j < к <г. Схематически окончательная компоновка должна иметь следующий вид:

<К

I г j г

42. [НМ32] Докажите, что для любого действительного числа с > О вероятность того, что алгоритм Q потребует менее (с -Ь 1)(Л -Ь 1)Hn сравнений при сортировке данных, меньше е~ (Верхняя грань представляет особый интерес, если задать условие, скажем, с =; N.)

43. [НМ21] Докажите, что уе - 1) dy + уе dy = -j. [Указание. Рассмотрите lima-+o+

44. [НМ24] Выведите формулу (37), как предложено в тексте настоящего раздела.

45. [НМ20] Объясните, почему при х > О справедливо равенство (43).

46. [НМ20] Каково значение выражения (1/27гг) Г(г)п~dz/{2- - 1) при условиях, что S - целое положительное число и О < а < s?

47. [НМ21] Докажите, что 5Zj.>j(n/2-)e-" - ограниченная функция от п.

48. [НМ24] Найдите асимптотическое значение величины V„, определенной в упр. 38, при помощи методов, аналогичных тем, которые в тексте настоящего раздела использовались для анализа величины Un, и получите члены до 0(1).

49. [НМ24] Продолжите асимптотическую формулу (47) для Un до членов порядка 0(п-1).

50. [НМ24] Найдите асимптотическое значение функции

t-E (:)(-»*

к>2

где т - произвольное фиксированное число, большее 1. (Эта функция при целом т, большем 2, потребуется для исследования общего случая обменной поразрядной сортировки, а также для анализа алгоритмов поиска в "памяти луча" в разделе 6.3.)

► 51. [НМ28] Покажите, что для вывода асимптотического разложения rk{m) можно воспользоваться методом исследования асимптотических задач при помощи гамма-функций вместо формулы суммирования Эйлера (см. (35)). (Это предоставляет единообразный способ анализа rk (т) при всех к без таких трюков, как введение в рассмотрение функции 3 i(x) = (е--1)/х.)

52. [НМЗЗ] (Н. Г. де Брейн.) Каково асимптотическое поведение суммы

где d{t) - количество делителей числа t? (Таким образом, d(l) = 1, d{2) = d(3) = 2, d{4) = 3, d(5) = 2 и т. д. Этот вопрос возникает в связи с анализом алгоритма прохождения дерева из упр. 2.3.1-11.) Найдите значение величины Sn/{) до членов порядка 0{п~).