Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 49
Текст из файла (страница 49)
Задачи 8.1. Вероятностные нижние границы сортировки сравнением В этой задаче мы докажем, что нижняя граница времени работы любого детерминистического или рандомизированного алгоритма сортировки сравнением при обработке и различных входных элементов равна П(п 1ки). Начнем с того, что рассмотрим детерминистическую сортировку сравнением А, которой соответствует дерево решений Тд. Предполагается, что все перестановки входных элементов А равновероятны. а. Предположим, что каждый лист дерева Тл помечен вероятностью его достижения при заданном случайном наборе входных данных.
Докажите, что ровно п! листьям соответствует вероятность 1/и1, а остальным — вероятность О. б. Пусть Р(Т) — длина внешнего пути дерева решений Т; другими словами, это сумма глубин всех листьев этого дерева. Пусть Т вЂ” дерево решений с й > 1 листьями и пусть 1Т и КТ вЂ” его левое и правое подлеревья. Покажите, что Р(Т) = Р(1,Т) + Р(ЯТ) + к. в. Пусть а(сс) — минимальная величина Р(Т) среди всех деревьев решений Т с й > 1 листьями. Покажите, что 4()с) = ш1п~<;<<я ~ (с((1) + с((~с — 1) + 1с).
(Указание; рассмотрите дерево решений Т с 8 листьями, на котором дости- 235 Глава В. Сортировка за линейное время гается минимум. Обозначьте количество листьев в йТ как Во, а количество листьев в ЯТ вЂ” как )е — Во.) г. Докажите, что для данного значения Й > 1 и 1 из диапазона 1 < 1 < Iе — 1 функция 11я1+ (!е — 1) !б(/е — 1) достигает минимума при 1 = !е/2. Выведите отсюда, что И(й) = П(й 1я й).
д. Докажите, что 0(ТВ) = Й(п! 1й(п!)), и выведите отсюда, что время сортировки п элементов в среднем случае составляет Й(п 1к и). Теперь рассмотрим рандомизированную сортировку В. Модель дерева решений можно обобщить таким образом, чтобы с ее помощью можно было рассматривать рандомизированные алгоритмы. Для этого в нее нужно включить узлы двух видов: обычные узлы сравнения и узлы нрандомизацни", которые моделируют случайный выбор вида КлмпОм(1, г) в алгоритме В; такой узел имеет т дочерних узлов, каждый из которых в процессе выполнения алгоритма может быть выбран с равной вероятностью. е. Покажите, что для любой рандомизированной сортировки сравнением В существует детерминистическая сортировка сравнением А, в которой ожидаемое количество сравнений не превышает количество сравнений в сортировке В. В.2.
Сортировка на месте за линейное время Предположим, что имеется массив, содержащий п записей с сортируемыми данными, и что ключ каждой записи принимает значения 0 илн 1. Алгоритм, предназначенный для сортировки такого набора записей, должен обладать некоторыми из трех перечисленных ниже характеристик.
1. Время работы алгоритма равно 0(п). 2. Алгоритм устойчив. 3. Сортировка выполняется на месте, т.е., кроме исходного массива, использу. ется дополнительное пространство, не превышаюшее некоторой постоянной величины. а Разработайте алгоритм, удовлетворяющий критериям 1 и 2.
б. Разработайте алгоритм, удовлетворяющий критериям 1 и 3. в. Разработайте алгоритм, удовлетворяющий критериям 2 и 3. г. Может ли какой-либо из разработанных вами в пп. (аКв) алгоритмов использоваться в строке 2 процедуры Клп!х-Яокт, чтобы последняя могла сортировать п записей с б-битовыми ключами за время 0(бп)? Поясните свой ответ. д. Предположим, что п записей обладают ключами, значения которых находятся в интервале от 1 до к. Покажите, как можно модифицировать алгоритм сортировки подсчетом, чтобы обеспечить сортировку этих записей на месте за Часть!!. Сортировка и корядковая статистика время 0(п + й).
В дополнение к входному массиву можно использовать дополнительную память объемом 0(й). Устойчив ли ваш алгоритм? (Указание: подумайте, как можно решить задачу для к = 3.) 8.3. Сортировка элементов переменной длины а. Имеется массив целых чисел, причем различные элементы этого массива могут иметь разные количества цифр; однако общее количество цифр во всех числах равно и. Покажите, как выполнить сортировку этого массива за время 0(п). б. Имеется массив строк, в котором различные строки могут иметь разную длину; однако общее количество символов во всех строках равно и.
Покажите, как выполнить сортировку этого массива за время 0(п). (Порядок сортировки в этой задаче определяется обычным алфавитным порядком, например а < аЬ < Ь.) 8.4. Кувшины длн воды Предположим, что имеется и красных и п синих кувшинов для воды, которые различаются формой и объемом. Все красные кувшины могут вместить разное количество воды; то же самое относится и к синим кувшинам.
Кроме того, каждому красному кувшину соответствует синий кувшин того же объема и наоборот. Задача заключается в том, чтобы разделить кувшины на пары, в каждой нз которых будут красный и синий кувшины одинакового обьема. Для этого можно использовать такую операцию; сформировать пару кувшинов, в которых один будет синим, а второй — красным, наполнить красный кувшин водой, а затем перелить ее в синий кувшин. Эта операция позволит узнать, какой из кувшинов больше илн является ли их объем одинаковым. Предположим, что для выполнения такой операции требуется одна единица времени. Необходимо сформулировать алгоритм, в котором для разделения кувшинов на пары производилось бы минимальное количество сравнений. Напомним, что непосредственно сравнивать два красных или два синих кувшина нельзя.
вь Опишите детерминистический алгоритм, в котором разделение кувшинов на пары производилось бы с помощью 9(пз) сравнений. б. Докажите, что нижняя граница количества сравнений, которые должен выпол- нить алгоритм, предназначенный для решения этой задачи, равна Й(п 1к и). в. Разработайте рандомизированный алгоритм, математическое ожидание количества сравнений в котором было бы равно 0(п 1я п), и докажите корректность этой границы.
Чему равно количество сравнений в этом алгоритме в наихудшем случае? Глава В. Сорт~ровна ла линейное ареал 737 8.5. Сортировка в среднем Предположим, что вместо сортировки массива нам нужно, чтобы его элементы возрастали в среднем. Точнее говоря, п-элементный массив А называется 'н-отсортированным, если для всех 1 = 1, 2,..., п — )е выполняется соотношение 2',*+",. ' А(7] 2 '+~+, А(2] к )е а Что представляет собой 1-отсортированный массив? б.
Приведите пример перестановки чисел 1, 2,..., 10, являющейся 2-отсортированной, но не отсортированной. в. Докажите, что п-элементный массив й-отсортирован тогда и только тогда, ко- гда для всех 1 = 1, 2,..., п — )е справедливо соотношение А(1] < А(в + )с]. * Разработайте алгоритм, который выполняет к-сортировку п-элементного массива за время 0(п 1й(п//е)) Можно также найти нижнюю границу для времени, необходимого для получения к-отсортированного массива, если /с — константа. д. Покажите, что к-сортировку массива длиной и можно выполнить за время 0(п 1к lс). (Указание: воспользуйтесь решением упр.
6.5.9.) е. Покажите, что если )е — жэнстанта, то для й-сортировки п-элементного массива потребуется время й(п1кп). (Указание: воспользуйтесь решением предыдущего задания вместе с нижней границей для алгоритмов сортировки сравнением.) б.б. Нижняя граница объединения отсортированных снискав Часто возникает задача объединения двух отсортированных списков. Эта процедура используется в качестве подпрограммы Мнксн в разделе 2.3.1.
В настоящей задаче мы покажем, что для количества сравнений, необходимых для обьединения двух п-элементных отсортированных списков в наихудшем случае, существует нижняя граница, равная 2п — 1 сравнениям. Сначала с помощью дерева решений покажем, что нижняя граница количества сравнений равна 2п — о(п). а Вычислите для заданных 2п чисел количество возможных способов их разделения на два отсортированных списка, каждый с п элементами. б.
Покажите с помощью дерева решений и вашего ответа к п. (а), что в любом алгоритме, корректно объединяющем два отсортированных списка, выполняется не менее 2п — о(п) сравнений. Теперь мы докажем наличие несколько более точной ~раницы 2п — 1. Часть П. Сортировка и порядковая статистика в. Покажите, что если два элемента, которые в объединенном списке будут расположены последовательно один за другим, принадлежат разным подлежащим объединению спискам, то в ходе объединения эти элементы обязательно придется сравнить. * С помощью решения предыдущего пункта задачи покажите, что нижняя граница для количества сравнений, которые производятся при объединении двух отсортированных списков, равна 2п — 1. В.
7. б-1-лемма сортировки и сортировка столбцами Операция сравнения с обменаи над двумя элементами массива А[1] и А[Я, где 1 < з, имеет следующий вид. СОМРАКЕ-Ехснххбе(А,1,1) 1 11А[1] > А[Я 2 Обменять А[1] с АЦ Мы знаем, что после операции сравнения с обменом А[1] < А[1]. Алгоритм сортировки сравнением с обменам без заяоминания работает с помощью исключительно последовательности операций сравнения с обменом. Индексы сравниваемых позиций в последовательности должны быть определены заранее, и хотя они могут зависеть от количества сортируемых элементов, они не могут зависеть ни от сортируемых значений, ни от результатов предшествующих операций сравнения.
Например, вот как сортировка вставкой выражается как алгоритм сортировки сравнением с обменом без запоминания. 1хзект10х-БОкт(А) 1 1ог з' = 2 то А. 1епдй 2 1ог г' = з' — 1 бозгпго 1 3 СОмРАке-ЕхснАх бе (А, 1, 1 + 1) б-1-лемма сортировки предоставляет мощное средство для доказательства того, что алгоритм сортировки сравнением с обменом без запоминания дает корректные результаты. Она гласит, что если этот алгоритм корректно сортирует все входные последовательности, состоящие из нулей и единиц, то он корректно сортирует все входные данные с произвольными значениями. Докажем О-1-лемму сортировки путем доказательства обратной к ней: если алгоритм сортировки сравнением с обменом без запоминания некорректно работает для входных данных с произвольными значениями, то он будет некорректно сортировать и некоторые О-! -входные данные.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
