Используя тождество

которое представляет собой частный случай соотношения 1.2.б-(20), можно легко определить сумму в (16):

(17)

2М V 2 У

В упр. 37 определено стандартное отклонение для В, но суммирование в (15) выполняется сложнее. По теореме 1.2.7А получим

х: ()(м - 1)-"я„=(i - ун - ММ)+б,

следовательно,

М / 1

А,,,е = M{Hn - In М) + 6, o<S<-[l--J . (18)

(Эта формула практически бесполезна, если М N. Более подробно асимптотическое поведение величины Aave при М = N/a обсуждается в упр. 40.)

Рассматривая совместно (17) и (18), можно получить общее время выполнения программы М при фиксированном М и iV -+ оо:

min ZIN -t- М + 2,

ave 1.75N/M + 31N - ЗМЯл -t- ЗМ In М -t- 4М - 3(J - 1.75N/M + 2, max 3.50iV2 + 24.5iV + 4M + 2. (19)

Заметим, что если М не слишком велико, то среднее время выполнения сокращается в М раз. При М = 10 сортировка будет осуществляться примерно в 10 раз быстрее, чем при М = 1. Однако максимальное время выполнения гораздо больше среднего. Таким образом, подтверждается важность выполнения условия равномерности распределения ключей, так как наихудший случай имеет место, когда все ключи попадают в один список.

Если положить М = N,to среднее время выполнения будет составлять примерно 34.36iV машинных циклов. При М = iV оно несколько больше, приблизительно 34.52iV машинных циклов, а при М = jN - приблизительно 48.04iV. (Заметим, что lOiV машинных циклов MIX при этом тратятся на одну лишь команду умножения!) Дополнительные затраты на сопровождающую программу из упр. 35, которая связывает воедино все М списков, увеличивают время выполнения приблизительно до 44.99iV, 41.95iV и 52.74N соответственно вариантам значения М. Таким образом, получен метод сортировки с временем работы порядка N при условии, что ключи довольно равномерно распределены в области возможных значений.

Пути дальнейшего совершенствования метода вставок в несколько списков обсуждаются ниже, в разделе 5.2.5.

УПРАЖНЕНИЯ

1. [10] Является ли алгоритм S алгоритмом "устойчивой" сортировки?

2. [11] Будет ли алгоритм S правильно сортировать числа, если на шаге S3 отношение К > Ki заменить отношением К > Ki?

3. [30] Является ли программа S самой короткой программой сортировки для машины MIX, или можно написать еш;е более короткую программу, которая давала бы тот же результат?

► 4. [Л/ЙО] Найдите минимальное и максимальное время выполнения программы S как функцию от N.

► 5. [М27] Найдите производящую функцию gN{z) - J2k>oPNkz для общего времени выполнения программы S, где pNk - вероятность того, что на выполнение программы S уйдет ровно к машинных циклов при заданной исходной случайной перестановке множества {1,2,... ,N}. Вычислите также стандартное отклонение времени выполнения для данного значения N.

6. [23] Для метода двухпутевых вставок, проиллюстрированного в табл. 2, по-видимому, необходимо, помимо области ввода, содержащей N записей, иметь область вывода, в которой может храниться 2N + 1 записей. Покажите, что можно выполнять двухпутевые вставки, имея в памяти как для ввода, так и для вывода пространство, достаточное для хранения всего 2N + 1 записей.

7. [М20] Пусть 01 02 ... о„ - случайная перестановка множества {1, 2,..., п}. Каково

среднее значение величины oi - 1 -f- о2 - 2 -I-----f- о„ - п? (Оно равно произведению п

и среднего чистого расстояния, на которое перемещается запись в процессе сортировки.)

8. [10] Является ли алгоритм D алгоритмом "устойчивой" сортировки?

9. [20] Какие значения А п В и какое общее время работы программы D соответствуют табл. 3 и 4? Проаналттруйте достоинства метода Шелла по сравнению с методом простых вставок в этом случае.

► 10. [22] В случае, когда Kj > К j-h, на шаге D3 алгоритм D предписывает выполнение множества ненужных действий. Покажите, как можно изменить программу D, чтобы избежать этих избыточных вычислений, и проанализируйте преимущества такой модификации.

11. [М10] Какой путь на решетке (аналогичной представленной на рис. 11) соответствует перестановке 1 2 5 3 7 4 8 6 9 11 10 12?

12. [М20] Докажите, что сумма вертикальных весов пути на решетке равна числу инверсий соответствующей 2-упорядоченной перестановки.

► 13. [iWifi] Поясните, как нужно приписать веса на решетке горизонтальным отрезкам вместо вертикальных, чтобы сумма горизонтальных весов пути на решетке равнялась числу инверсий в соответствующей 2-упорядоченной перестановке.

14. [М28] (а) Покажите, что для сумм, определяемых равенством (2), действительно А2п+\ = 2А2п. (Ь) Если положить г = s, t = -2, то обобщенное тождество в упр. 1.2.6-26 упрощается и приводится к виду

- х/1 - 4г 2z )

Проанализировав сумму Лгп", покажите, что

A2n=n4-\

► 15. [НМЗЗ] Пусть gn{z), g„{z), hn{z) и /1„(г) равны J""""* "у™, где сумма берется по всем путям длиной 2п на решетке от (0,0) до {п,п), где веса определяются, как на рис. 11, а пути удовлетворяют некоторым ограничениям на вершины, через которые эти пути проходят. Для h„(z) нет ограничений, но для g„(z) пути не должны проходить через вершины такие, что i > j; hn{z) и gn{z) определяются аналогично, но не допускаются также и вершины (г, i) при О < г < п. Таким образом,

go{z) = \, gi{z) = z, 52(2) = / +gi(z) = z, 32(2) =

/lo(z) = l, hi{z) = z + l, /l2(z) = z+z + 3z + l;

hliz)=z + l, h2iz) = Z+Z.

Найдите рекуррентные соотношения, определяюш;ие эти функции; и воспользуйтесь полученными рекуррентными соотношениями для доказательства равенства

Oi)+/.;(i) = l±i(;).

(Отсюда легко можно найти точную формулу дисперсии числа инверсий в случайной 2-упорядоченной перестановке множества {1,2,..., 2п};.она асимптотически приближгйтся

16. Найдите формулу максимального числа инверсий в Л-упорядоченной перестановке множества {1,2, Каково максимально возможное число перезаписей при выполнении алгоритма D, если значения смеш;ений для сортировки удовлетворяют условию делимости (5)?

17. [Л/ЙТ] Покажите, что если N = 2* и hs - 2 при i > s > О, то суш;ествует единственная перестановка множества {1,2,..., п}, максимизируюш;ая число перемеш,ений записей при выполнении алгоритма D. Найдите простой способ описания этой перестановки.

18. [НМ24] При больших значениях N сумму (6) можно считать равной

4 ht-i 8 \ ht-2 ho

Каковы действительные значения ht-i,..., Ло, минимизируюш;ие это выражение, если N и t фиксированы, а /го = 1?

► 19. [М25] Каково среднее значение величины А в анализе времени работы программы D, если значения смещений при сортировке удовлетворяют условию делимости (5)?

20. [М22] Покажите, что теорема К следует из леммы L.

21. [М25] Пусть Л и/г - взаимно простые целые положительные числа. Будем говорить, что целое число - породкдаемое, если оно равно xh + yk при некоторых неотрицательных целых Хк и ук- Покажите, что п является порождгймым тогда и только тогда, когда hk - h - к - п - не порождаемое. (Поскольку О - наименьшее порождаемое целое, наибольшее не порождаемое должно, таким образом, быть равно hk - h - к. Отсюда следует, что в любом массиве, который является одновременно и Л-, и /г-упорядоченным, Ki < Kj, если только j - i> [h- 1){к - 1).)

22. [МЗО] Докажите, что любое целое число > 2(2* - 1) можно представить в виде

ао(2 - 1) + al(2+ - 1) + 02(2+ -!) + ••,