Задачи к главе 9

183

Р{Х ж}. Предположим, что на вход алгоритма поступает последовательность из га чисел, которые являются независимыми случайными величинами с функцией распределения Р. Функция Р непрерывна и может быть вычислена за время 0(1). Как отсортировать такую последовательность, чтобы среднее время сортировки линейно зависело от га?

Задачи

9-1 Нижние оценки для среднего числа сравнений

В этой задаче мы докажем, что среднее время работы любого детерминированного или вероятностного алгоритма сортировки га чисел, основанного на сравнениях, есть fi(ralgra). Начнем с того, что рассмотрим детерминированный алгоритм А, основанный на сравнениях; пусть Тд - его разрешающее дерево. Мы предполагаем, что все перестановки входной последовательности равновероятны.

а.Напишем на каждом листе дерева Тд вероятность того, что алгоритм завершится в этом листе. Покажите, что в га! листах написано 1/га!, а в остальных листах написан нуль.

б.Обозначим через D(T) сумму глубин всех листьев в двоичном дереве Г (мы предполагаем, что каждая вершина либо является листом, либо имеет двух детей - так устроены разрешающие деревья). Пусть Г - дерево с k > 1 листьями, и пусть через LT и RT обозначены левое и правое поддеревья. Покажите, что D(T) = D(LT) + D(RT) + к.

в.Пусть d(m) - наименьшее значение числа D(T) среди всех деревьев Т с т листьями. Покажите, что d(k) = mini8 i{d(i) + d(k - г) + к}. (Указание: дерево LT может содержать от 1 до к - 1 листьев.)

г.Покажите, что для фиксированного к выражение г lg г + (к - г) \g(k - г) достигает минимума на отрезке от 1 до к - 1 в точке г = к/2. Выведите отсюда, что d(k) = Q(klgk).

д.Покажите, что 0(Гд) = £7(га! lg(ra!)), и выведите отсюда, что время сортировки га чисел с помощью разрешающего дерева Гд, усреднённое по всем перестановкам на входе, есть Q(гаlgra).

Теперь рассмотрим вероятностный алгоритм В, основанный на сравнениях. Его можно описать с помощью разрешающего дерева, в котором бывают узлы двух типов: соответствующие сравнениям и случайным выборам. В узлах второго типа происходит вызов процедуры Random(1,t); у такого узла г детей, каждый из которых выбирается с равной вероятностью. (Для разных узлов число г может быть разным.)

е.Пусть имеется вероятностный алгоритм сортировки В. Для

каждой перестановки на входе найдём математическое ожидание числа сравнений. Усредним эти ожидания по всем входам; получится некоторое число Т. Покажите, что существует детерминированный алгоритм А, у которого среднее (по всем перестановкам на входе) число сравнений не превосходит Т. Выведите отсюда, что для любого вероятностного алгоритма максимальное (по всем входам) математическое ожидание числа сравнений есть Q(гаlgra).

(Указание. Если среднее по всем входам и всем вариантам случайных чисел равно Г, то существует такой набор случайных чисел, при котором среднее по всем входам не больше Г.)

9-2 Сортировка без дополнительной памяти за линейное время

а.Пусть нам дан массив записей, который необходимо отсортировать по ключу, принимающему значение 0 или 1. Придумайте простой алгоритм, осуществляющий такую сортировку за линейное время и использующий дополнительную память 0(1) (иными словами, объем дополнительной памяти не зависит от размеров сортируемого массива).

б.Можно ли воспользоваться алгоритмом из пункта (а) для цифровой сортировки по 6-битному ключу за время О (6га)? Объясните свой ответ.

в.Пусть га записей надо отсортировать по ключу, принимающему целые значения от 1 до к. Как модифицировать сортировку подсчётом, чтобы можно было отсортировать эти записи за время 0(п-\-к), и при этом объем используемой памяти (помимо сортируемого массива) был О (к)? (Указание. Начните со случая к = 3.)

Замечания

Анализ алгоритмов сортировки с помощью разрешающих деревьев был предложен Фордом и Джонсоном [72]. В фундаментальной книге Кнута [123], посвященной сортировке, рассматриваются многочисленные варианты этой задачи и доказывается нижняя оценка числа сравнений (приведённая в этой главе). Нижние оценки для задачи сортировки и различных обобщений разрешающих деревьев подробно изучались Бен-Ором [23].

Согласно Кнуту, заслуга изобретения сортировки подсчётом (1954 год) и её комбинации с цифровой сортировкой принадлежит Сьюарду (H.H.Seward). Сама же цифровая сортировка, видимо, давно применялась для сортировки перфокарт. Кнут утверждает, что первое печатное описание этого метода появилось в 1929 году в качестве составной части руководства по оборудованию для работы с перфокартами, написанного Комри (L. J. Comrie). Сортировка вычерпыванием используется с 1956 года, когда Айзек (E.J.Isaac)

и Синглетон (R. С. Singleton) предложили основную идею.