7.Сложность алгоритмов некоторых задач.
Данный раздел содержит примеры алгоритмов, иллюстрирующих проведенные выше рассуждения. Также алгоритмы и задачи этого разделы будут использованы в дальнейшем при обсуждении классов сложности задач. Этот раздел ни в коем случае не является попыткой обзора алгоритмов и методов их построения. (Такая попытка сделана, например, в [5], а монографии [1] и [4] целиком посвящены описанию алгоритмов и методов их построения). Более того, примеры этого раздела в большинстве своем либо очевидны, либо знакомы вам из курса дискретной математики.
Далее коротко приводится алгоритм и оценка его сложности «в худшем». Описание задач, а также обозначение их параметров приведены выше.
7.1.Задача нахождения максимального числа.
Решение дает очевидный простой алгоритм: последовательно сравниваем числа и в отдельной ячейке храним максимальное из просмотренных. Для решения необходимо просмотреть все числа, т.е. сделать не менее n-1 сравнений. Но за n-1 сравнений мы найдем решение задачи. Поэтому данный алгоритм позволяет найти сложность задачи, т.е сложность алгоритма - O(n) является одновременно и сложностью задачи нахождения максимального числа. Верхняя и нижняя оценка сложности совпадают.
7.2.Задача сортировки.
В дискретной математике сортировке подлежат объекты разной природы. Пусть необходимо отсортировать (например, по возрастанию) числовой массив из n элементов. Без ограничения общности будем считать, что – степень двойки (чтобы не возиться с целыми частями). В качестве элементарной операции используется операция сравнения чисел. Чтобы сравнивать числа нужно их различать как объекты сортировки (эти объекты имеют численные значения). Сравнение – это операция с результатом «да» или «нет», поэтому кодируем объекты сортировки бинарными последовательностями. Какова минимальная длина такой последовательности для множества их M элементов? Очевидно, что это log M. В теории информации этот факт известен как энтропия по Хартли.
Если мы упорядочиваем n объектов (чисел), то в зависимости от их значений можно получить n! различных упорядочиваний. Последовательность сравнений для их различения не может быть меньше log(n!). Применяем формулу Стирлинга: log(n!)=(n+1/2)logn-n+0,5log2 (n)+α/(12n), 0< α <1, n→∞ . Отсюда следует, что задачу сортировки нельзя решить со сложностью алгоритма, меньшей O(nlogn).
C 1950-х годов разработано много методов сортировки со сложностью алгоритма, равной O(nlogn). Приведем один из них (см., например, [1]). Он использует процедуру СЛИЯНИЕ(S,T) слияние в один упорядоченный массив (S,T) двух упорядоченных массивов S и T. Поскольку исходные массивы упорядочены, эта процедура требует не более |S|+|T|-1 сравнений. Массив (S,T) формируется путем переноса туда элементов из S, T. Вначале переносится наибольший элемент массивов S, T, затем следующий и т.д. В случае равенства значений предпочтение отдается, например, массиву S. Эта процедура применяется внутри процедуры СОРТ(i,j), выполняющей сортировку для последовательности xi,xi+1,…,xj в предположении, что длина этой последовательности – степень двойки. Схема приведена ниже.
Procedure СОРТ(i,j):
If i=j then return xi
else
begin
m=(i+j-1)/2; СЛИЯНИЕ(СОРТ(i,m), СОРТ(m+1,j))
return
end
Таким образом сортировка исходной последовательности – это вызов процедуры СОРТ(1,n).
Пусть T(n) – время работы программы на массиве длины n. Тогда из описания процедур следует рекуррентное соотношение
Решением этого рекуррентного соотношения является функция T(n)=O(nlogn).
Если требования на длину массива снять (это требование характеризует, так называемые, сбалансированные массивы), то получается O(n2), но этот рост убирается дальнейшим усложнением процедуры. Сегодня известно множество различных алгоритмов сортировки сложности O(nlogn).