Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 47
Текст из файла (страница 47)
Упражнения 8.4-1. Используя в качестве модели рис. 8.4, проиллюстрируйте обработку алгоритмом Висквт 8окт массива А = (079,013,016,064,039,020,089, 0.53, 0.71, 0.42). 8.4-2. Чему равно время работы алгоритма карманной сортировки в наихудшем случае? Какое простое изменение следует внести в этот алгоритм, чтобы его ожидаемое время работы осталось линейным, а время работы в наихудшем случае стало равным О (и 18 и)? *8.4-3. Функция расярсделеиия вероятности Р(х) случайной величины Х определяется с помощью соотношения Р (х) = Рг (Х < х). Предположим, что на вход алгоритма поступает последовательность из п случайных величин ХПХз,...,Х„с непрерывной функцией распределения Р, значение которой вычисляется в течение времени О (1). Покажите, каким образом выполнить сортировку этих величин, чтобы математическое ожидание времени выполнения процедуры линейно зависело от их количества.
Задачи 8-1. Нижние оценки для сортировки сравнением в среднем случае В этой задаче мы докажем, что нижняя граница математического ожидания времени работы любого детерминистического или рандомизированного алгоритма сортировки сравнением при обработке и различающихся входных элементов равна П (и 18 и). Начнем с того„что рассмотрим детерминистическую сортировку сравнением А, которой соответствует дерево решений Тд.
Предполагается, что все перестановки входных элементов А равновероятны. а) Предположим, что каждый лист дерева Тд помечен вероятностью его достижения при заданном случайном наборе входных данных. Глава 8. Сортировка за линейное время 235 Докажите, что ровно п1 листьям соответствует вероятность 1/п1, а остальным — вероятность О. б) Пусть Р (Т) — длина внешнего пути дерева решений Т; другими словами, это сумма глубин всех листьев этого дерева. Пусть Т— дерево решений с )с > 1 листьями, а РТ и ВТ вЂ” его левое и правое поддеревья.
Покажите, что Р (Т) = Р (РТ) + Р (ЯТ) + lс. в) Пусть Н (к) — минимальная величина Р (Т) среди всех деревьев решенийТсlс > 1листьями. Покажите,чтод(lс) = шшз«;ь ~(Н(г)+ + Н (1с — г) + к). (Указание: рассмотрите дерево решений Т с )с листьями, на котором достигается минимум. Обозначьте количество листьев в РТ через гс, а количество листьев в ЯТ вЂ” через й — го.) г) Докажите, что для данного )с > 1 и ю' из диапазона 1 < г < )с — 1 функция Г 1к Г + (Й вЂ” г) 1к (Й вЂ” г) достигает минимума при г = Й/2.
Выведите отсюда, что д(к) = й(й18к). д) Докажите, что справедливо соотношение Р (Тд) = й(п! 18(п1)), и выведите отсюда, что математическое ожидание времени сортировки и элементов равно й (и 18 и). А теперь рассмотрим рандаиизированную сортировку В. Модель дерева решений можно обобщить таким образом, чтобы с ее помощью можно было рассматривать рандомизированные алгоритмы. Для этого в нее нужно включить узлы двух видов: обычные узлы сравнения и узлы "рандомизации", которые моделируют случайный выбор вида Клипом(1, г) в алгоритме В; такой узел имеет г дочерних узлов, каждый из которых в процессе выполнения алгоритма может быть выбран с равной вероятностью.
е) Покажите, что для любой рандомизированной сортировки сравнением В существует детерминистическая сортировка сравнением А, в которой в среднем производится не больше сравнений, чем в сортировке В. 8-2. Сортировка на месте за линейное время Предположим, что у нас имеется массив, содержащий п записей с сортируемыми данными, и что ключ каждой записи принимает значения О или 1. Алгоритм„предназначенный для сортировки такого набора записей, должен обладать некоторыми из трех перечисленных ниже характеристик. 1) Время работы алгоритма равно 0 (и). 2) Алгоритм обладает свойством устойчивости. 236 Часть й.
Сортировка и порядковая статистика 3) Сортировка производится на месте, т.е. кроме исходного массива используется дополнительное пространство, не превышающее некоторой постоянной величины. а) Разработайте алгоритм, удовлетворяющий критериям 1 и 2. б) Разработайте алгоритм, удовлетворяющий критериям 1 и 3. в) Разработайте алгоритм, удовлетворяющий критериям 2 и 3. г) Может ли какой-либо из представленных в частях а)-в) алгоритмов обеспечить поразрядную сортировку п записей с Ь-битовымн ключами за время О (Ьп)? Поясните, почему. д) Предположим, что и записей обладают ключами, значения которых находятся в интервале от 1 до 1с.
Покажите, как можно модифицировать алгоритм сортировки подсчетом, чтобы обеспечить сортировку этих записей на месте в течение времени О (и+ к). В дополнение к входному массиву, можно использовать дополнительную память объемом О (1с). Устойчив ли этот алгоритм? (Указание: подумайте, как можно решить задачу для к = 3.) 8-3.
Сортировка элементов переменной длины а) Имеется массив целых чисел, причем различные элементы этого массива могут иметь разные количества цифр; однако общее количество цифр во всех числах равно и. Покажите, как выполнить сортировку этого массива за время О (и). б) Имеется массив строк, в котором различные строки могут иметь разную длину; однако общее количество символов во всех строках равно п.
Покажите, как выполнить сортировку этого массива за время О (и). (Порядок сортировки в этой задаче определяется обычным алфавитным порядюм; например, а < аЬ < Ь.) 8-4. Кувшины для воды Предположим, имеется и красных и и синих кувшинов для воды, которые различаются формой и объемом.
Все красные кувшины могут вместить разное количество воды; то же относится и к синим кувшинам. Кроме того, каждому красному кувшину соответствует синий кувшин того же объема и наоборот. Задача заключается в том, чтобы разбить кувшины на пары, в каждой из юторых будут красный и синий кувшин одинакового обьема. Для этого можно использовать такую операцию: сформировать пару кувшинов, в которых один будет синим, а второй — красным, наполнить красный Глава 8.
Сортировка за линейное время 237 кувшин водой, а затем перелить ее в синий кувшин. Эта операция позволит узнать, какой из кувшинов больше или является ли их объем одинаковым. Предположим, что для выполнения такой операции требуется одна единица времени. Необходимо сформулировать алгоритм, в котором для разбиения кувшинов на пары производилось бы минимальное количество сравнений. Напомним, что непосредственно сравнивать два красных или два синих кувшина нельзя. а) Опишите детерминистический алгоритм, в котором разбиение кувшинов на пары производилось бы с помощью 9 (пз] сравнений. б) Докажите, что нижняя граница количества сравнений, которые должен выполнить алгоритм, предназначенный для решения этой задачи, равна Й(п 18 п). в) Разработайте рандомнзированный алгоритм, математическое ожидание количества сравнений в котором было бы равно О (п18п), и докажите корректность этой границы.
Чему равно количество сравнений в этом алгоритме в наихудшем случае? 8-5. Сортировка в среднем Предположим, что вместо сортировки массива нам нужно, чтобы его элементы возрастали в среднем. Точнее говоря, п-элементный массив А называется )сотсортировааньим, если для всех г = 1,2,...,п — )с выполняется такое соотношение: А [?] 2„А [Я а) Что из себя представляет 1-отсортированный массив? б) Приведите пример перестановки чисел 1, 2, ..., 10, являющейся 2-отсортированной, но ае отсортированной.
в) Докажите, что п-элементный массив К-отсортировав тогда и только тогда, когда для всех г = 1,2,., и — /с справедливо соотношение А [1] ( А [1 + 1с]. г) Разработайте алгоритм, который выполняет й-сортировку и-элементного массива за время О (и 18 (и/й)). Можно также найти нижнюю границу для времени„необходимого для получения Й-отсортированного массива, если Й вЂ” константа. д) Покажите, что й-сортировку массива длины п можно выполнить за время О (п 18 lс). (Указание: воспользуйтесь решением упражнения 6.5-8.) Часть!1. Сортировка и порядковая статистика 238 е) Покажите, что если й — константа, то для й-сортировки и-элеменгного массива потребуется время П (п18п).
(Указание: воспользуйтесь решением предыдущего задания вместе с нижней границей для алгоритмов сортировки сравнением.) 8-6. Нижняя граница для объединения отсортированных списков Часто возникает задача объединения двух отсортированных списков. Эта процедура используется в качестве подпрограммы в процедуре МЕККЕ БОКт; она описана в разделе 2.3.1, где получила имя МЕКСЕ. В настоящей задаче мы покажем, что для количества сравнений, необходимых для объединения двух и-элементных отсортированных списков в наихудшем случае, существует нижняя граница, равная 2и — 1 сравнениям. Сначала с помощью дерева решений покажем, что нижняя граница количества сравнений равна 2п — о (и).
а) Покажите, что всего имеется (~„") способов разбиения 2п чисел на два отсортированных списка, в каждом из которых и чисел. б) Покажите с помощью дерева решений, что в любом алгоритме, корректно объединяющем два отсортированных списка, выполняется не менее 2и — о (и) сравнений. Теперь мы докажем наличие несколько более точной границы 2п — 1. в) Покажите, что если два элемента, которые в объединенном списке будут расположены последовательно один за другим, принадлежат разным подлежащим обьединению спискам, то в ходе объединения эти элементы обязательно придется сравнить. г) С помощью ответа на предыдущий пункт задачи покажите, что нижняя граница для количества сравнений, которые производятся прн объединении двух отсортированных списков, равна 2и — 1.
Заключительные замечания Использовать модель дерева решений при изучении алгоритмов сортировки сравнением впервые предложили Форд (гогд) и Джонсон (1о)шзоп) 194). В томе Искусства лрогральннрования Кнута (Кпш)з), посвященном сортировке [185), описываются различные разновидности задачи сортировки, включая приведенную здесь теоретико-информационную нижнюю границу для сложности сортировки. Полное исследование нижних границ сортировки с помощью обобщений модели дерева решений было проведено Бен-Ором (Вел-Ог) 136).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
