Функции и заданы таблицами истинности (табл. 9, табл. 10). Построить таблицу истинности суперпозиции
.
Таблица 9 Таблица 10
Решение. Построим таблицу истинности функции (табл. 11).
Таблица 11
3 q := ;
4 Merge-Sort(A, p, q);
5Merge-Sort(A, q+1, r);
6 Merge (A, p, q, r);
Весь массив можно отсортировать вызовом Merge-Sort(A, 1, length(A)). Если длина массива п = length(A)есть степень двойки, то в процессе сортировки произойдёт слияние пар элементов в отсортированные участки длины 2, затем слияние пар таких участков в отсортированные участки длины 4 и так далее до n (на последнем шаге соединяются два отсортированных участка длины ).
1.3.2. Анализ алгоритмов типа «разделяй и властвуй»
При вычислении сложности такого алгоритма необходимо учесть время, затрачиваемое на рекурсивные вызовы, поэтому получается некоторое рекуррентное соотношение. Далее, исходя из этого соотношения, требуется оценить общее время работы.
Предположим, что алгоритм разбивает задачу размера п на а подзадач, каждая из которых имеет в b раз меньший размер. Будем считать, что разбиение требует времени D(n), а соединение полученных решений — времени С(п). Тогда получаем соотношение для времени работы Т(п)в худшем случае на задачах размера п: Т(п) = аТ(п / b) + D(n) + C(n). Это соотношение выполнено для достаточно больших п,именно в этих случаях задачу имеет смысл разбивать на подзадачи. Для малых п,когда такое разбиение невозможно или нецелесообразно, применяется некоторый прямой метод решения. Поскольку п ограничено, то время работы также не превосходит некоторой константы.
Анализ сортировки слиянием
Для простоты будем предполагать, что размер массива n есть степень двойки. Как мы увидим в дальнейшем, это ограничение не очень существенно. Тогда на каждом шаге сортируемый участок делится на две равные части. Одно такое разбиение (т.е. вычисление границы) требует времени , а слияние — . В результате получаем соотношение
.
В дальнейшем будет показано, что из этого соотношения следует , где через мы обозначаем двоичный логарифм. Заметим, что в подобных выражениях основание логарифма не играет роли, так как его изменение приводит лишь к изменению константы-множителя. Таким образом, для больших п сортировка слиянием эффективнее сортировки вставками, которая требует времени .
Упражнения
1.3-1.Покажите работу сортировки слиянием для массива
А = (3,41,52,26,38,57,9,49).
1.3-2.Напишите текст процедуры Merge(A, p, q, r).
1.3-3. Докажите по индукции, что если
,
то (при всех n, являющихся степенями двойки).
1.3-4.Сортировку вставками можно оформить в виде рекурсивной процедуры: желая отсортировать A[n], мы рекурсивно сортируем А[1..п-1], а затем A[n] ставим на правильное место в отсортированном массиве А[1..п-1]. Напишите рекуррентное соотношение для времени работы такой процедуры.
1.3-5.Возвращаясь к задаче поиска (упр. 1.1-3), заметим, что при поиске в отсортированном массиве мы можем сначала сравнить искомый элемент со средним элементом массива и узнать, в какой половине его следует искать, а затем применить ту же идею рекурсивно. Такой способ называется двоичным поиском. Напишите соответствующую процедуру, используя цикл или рекурсию. Объясните, почему время её работы есть .
1.3-6. Заметим, что цикл whileв строках 5-9 процедуры Insertion-Sort просматривает элементы отсортированного участка А[1..j-1] подряд. Вместо этого можно было бы использовать двоичный поиск, чтобы найти место вставки за время . Удастся ли таким образом сделать общее время работы равным ?
1.3-7*Дан массив S из n действительных чисел, а также число х. Как за время определить, можно ли представить x в виде суммы двух элементов массива S?
1.4. О пользе быстрых алгоритмов
Часто разница между хорошим и плохим алгоритмом более существенна, чем между быстрым и медленным компьютером. Предположим, что требуется отсортировать массив из миллиона чисел. Что быстрее — сортировать его вставками на суперкомпьютере (100 миллионов операций в секунду) или слиянием на домашнем компьютере (1 миллион операций)? Предположим также, что сортировка вставками экономично написана на ассемблере, и для сортировки n чисел нужно лишь операций. В то же время алгоритм слиянием написан без особенной заботы об эффективности и требует операций. Тогда при сортировке миллиона чисел получится
на суперкомпьютере;
на домашнем компьютере.
Отсюда следует, что разработка эффективных алгоритмов не менее важна, чем разработка быстрой электроники.
Упражнения
1.4-1.Пусть сортировки вставками и слиянием выполняются на одной и той же машине и требуют и операций соответственно. Для каких значений п сортировка вставками является более эффективной? Как можно улучшить алгоритм сортировки слиянием?
Пусть имеется алгоритм, решающий задачу размера п за f(n)микросекунд (1мкс = сек.). Каков максимальный размер задачи, которую он сможет решить за время t? Найти его для функций и времён, перечисленных в таблице.
1 сек
1 мин
1 час
1 день
1 месяц
1 год
1 век
log n
п
nlogn
n!
1-2. Сортировка вставками для коротких участков
Асимптотически сортировка слиянием быстрее сортировки вставками, но для малых п соотношение обратное. Поэтому имеет смысл достаточно короткие участки не разбивать дальше, а применять к ним сортировку вставками. Вопрос в том, где следует провести границу.
а. Пусть массив размера п разбит на частей размера к. Покажите, что можно отсортировать все части по отдельности (с помощью сортировки вставками) за время .
б. Покажите, что после этого можно слить все части в один упорядоченный массив за время .
в. Тем самым общее время работы такого смешанного алгоритма есть . Какова максимальная скорость роста к как функции от п,при которой это время по-прежнему есть ?
г. Как бы вы стали выбирать оптимальное значение k на практике?
1-3. Число инверсий
Пусть А[1..п]— массив из п различных чисел. Нас интересует количество инверсийв этом массиве, т.е. число пар i < j. для которых A[i] > A[j].
а. Укажите пять инверсий в массиве (2,3,8,6,1).
б. Каково максимально возможное число инверсий в массиве длины n?
в. Как связано время работы алгоритма сортировки вставками и число инверсий? Объясните свой ответ.
г. Постройте алгоритм, который считает число инверсий в массиве длины n за время . (Указание: модифицируйте алгоритм сортировки слиянием.)
и 
заданы таблицами истинности (табл. 9, табл. 10). Построить таблицу истинности суперпозиции
.
(табл. 11).
;
).
, а слияние — 
. В результате получаем соотношение
.
, где через 
мы обозначаем двоичный логарифм. Заметим, что в подобных выражениях основание логарифма не играет роли, так как его изменение приводит лишь к изменению константы-множителя. Таким образом, для больших п сортировка слиянием эффективнее сортировки вставками, которая требует времени 
.
,
(при всех n, являющихся степенями двойки).
.
?
операций. В то же время алгоритм слиянием написан без особенной заботы об эффективности и требует 
операций. Тогда при сортировке миллиона чисел получится
на суперкомпьютере;
на домашнем компьютере.
и 
операций соответственно. Для каких значений п сортировка вставками является более эффективной? Как можно улучшить алгоритм сортировки слиянием?
операций, эффективнее алгоритма, требующего 
операций?
сек.). Каков максимальный размер задачи, которую он сможет решить за время t? Найти его для функций и времён, перечисленных в таблице.
частей размера к. Покажите, что можно отсортировать все части по отдельности (с помощью сортировки вставками) за время 
.
.
. Какова максимальная скорость роста к как функции от п,при которой это время по-прежнему есть