Упражнения

1.3-1 Пусть сортировки вставками и слиянием исполняются на одной и той же машине и требуют 8га2 и 64га log га соответственно. Для каких значений га сортировка вставками является более эффективной? Как можно улучшить алгоритм сортировки слиянием?

1.3-2 При каком наименьшем значении га алгоритм, делающий 100га2 операций, эффективнее алгоритма, делающего 2п операций?

Задачи

1-1 Сравнение времени работы

Пусть имеется алгоритм, решающий задачу размера га за /(га) микросекунд. Каков максимальный размер задачи, которую он сможет решить за время tl Найти его для функций и времён, перечисленных в таблице.

1-2 Сортировка вставками для коротких кусков

Асимптотически сортировка слиянием быстрее сортировки вставками, но для малых га соотношение обратное. Поэтому имеет смысл достаточно короткие куски не разбивать дальше, а применять к ним сортировку вставками. Вопрос в том, где следует провести границу.

а.Пусть массив длины га разбит на к частей размера п/к. Покажите, что можно отсортировать все части по отдельности (с помощью сортировки вставками) за время Q(nk).

б.Покажите, что после этого можно слить все части в один упорядоченный массив за время 0(ralog(ra/£;)).

в.Тем самым общее время работы такого смешанного алгоритма есть в (пк + га log (п/к)). Какова максимальная скорость роста к как функции от га, при котором это время по-прежнему есть 0(ralog га)?

г.Как бы вы стали выбирать оптимальное значение к на прак-

тике?

1-3 Число инверсий

Пусть А[1..п] - массив из га различных чисел. Нас будет интересовать количество инверсий (inversions) в этом массиве, т.е. число пар г < j, для которых A[i] > A[j].

а.Укажите пять инверсий в массиве (2, 3, 8, 6,1).

б.Каково максимально возможное число инверсий в массиве длины га?

в.Как связано время работы алгоритма сортировки вставками и число инверсий? Объясните свой ответ.

г.Постройте алгоритм, который считает число инверсий в массиве длины га за время О (га log га). (Указание: Модифицируйте алгоритм сортировки слиянием.)

Замечания

Есть множество хороших книг о построении алгоритмов. Вот некоторые из них: Ахо, Хопкрофт и Ульман [4,5], Баас [14], Брас-сар и Бретли [14], Хоровиц и Сахни [105], Кнут [121, 122, 123], Манбер [142], Мельхорн [144, 145, 146], Пурдом и Браун [164], Рейнгольд, Нивергельт и Део [167], Седжвик [175], Уилф [201]. Практические аспекты разработки эффективных алгоритмов: Бентли [24,25], Гоннет [90].

В 1968 году Кнут опубликовал первый из трёх томов серии Искусство программирования для ЭВМ [121, 122, 123], который стал началом новой эпохи в науке об эффективных алгоритмах. Все три тома до сих пор остаются незаменимым справочником. Как пишет Кнут, слово «алгоритм» происходит от имени арабского математика девятого века Ал-Хорезми (al-Khowarizmi, или al-Khwarizmi).

Ахо, Хопкрофт и Ульман [4] указали на важность асимптотического анализа времени работы как средства сравнения эффективности алгоритмов. Они широко использовали рекуррентные соотношения для получения оценок времени работы.

Книга Кнута [123] содержит исчерпывающее изложение множества алгоритмов сортировки. Он сравнивает различные алгоритмы, точно подсчитывая число различных шагов (мы делали это для сортировки сравнением). Рассматриваются различные варианты сортировки вставками, включая сортировку Шелла (D. L. Shell), которая использует сортировку подпоследовательностей с постоянным шагом для уменьшения числа операций.

Сортировка слиянием также описана в книге Кнута, который указывает, что механическое устройство для слияния двух стопок перфокарт за один проход было изобретено в 1938 году. По-

видимому, Джон фон Нейман (J. von Neumann), один из основателей информатики, написал программу сортировки слиянием для компьютера EDVAC в 1945 году.