С.А. Абрамов - Вычислительная сложность алгоритмов, страница 5

Транспонирование матрицы:for i=1 to n-1 dofor j=i+1 to n do aij ↔ aji ododn2 − nЕсли хотим посчитать число обменов, то оно равно ∑ ∑1 = ∑ (n − i ) = ∑ i =.2i =1 j =i +1i =1i =1n −1n −1nn −1Рассмотрим ещё один алгоритм:l:=0;(n)64ϕ7483for i=1 ton + 1 dok:=i;⎣⎦⎢k ⎥while k>1 do l:=l+k; k:= ⎢ ⎥ od⎣3⎦odТребуется оценить сложность приведённого алгоритма.Очевидно, что внутренний цикл while можно оценить через Θ(log i) , т.к. количество егоитераций совпадает с log 3 i . Поэтому для сложности алгоритма в целом справедлива оценка:⎛ ϕ (n)⎞T (n) = Θ⎜⎜ ∑ log i ⎟⎟ = Θ(log ϕ (n)!) = Θ(ϕ (n) log ϕ (n) ) и с учётом ϕ (n) =⎝ i=1⎠T ( n) = Θ(⎣ n + 1⎦log3)(⎣ n + 1⎦ получаем:3)n3 + 1 = Θ n3 2 log n .До сих пор в качестве размера входа мы использовали целые числа, но определение размеравхода, вообще говоря, допускает использование и рациональных, и иррациональных чисел.a0.

Ранееa1было получено, что TE (n) = Θ(log a1 ) . Рассмотрим следующую последовательность размеровFвхода: rn = n+1 , где Fi — числа Фибоначчи. Из формулы Бене следует, чтоFnПример. В алгоритме Евклида в качестве входа возьмём рациональное число r =1+ 5Fn+1, при этом сложность с ростом n становится всё больше и больше. Если и→φ =Fn2удастся установить оценку TE′ (r ) < f (r ) , то, очевидно, что f (r ) будет разрывная. Более того,если берём интервал (a, b) , то для любого наперёд заданного N , найдётся рациональноеaчисло r такое, что r = 0 и алгоритму Евклида для чисел (a0 , a1 ) потребуется N шагов.a1Для целых размеров входа таких фокусов нет.Следует отметить, что существуют алгоритмы, для которых целесообразно выбрать вкачестве размера входа нецелое число. Например, алгоритм поиска решения уравнения наотрезке методом деления пополам.

Для поиска решения с точностью ε потребуется22log 21ε+ O(1) операций, и в качестве размера входа здесь целесообразно взять величину1⎞⎛Для метода касательных сложность составит O⎜ log log ⎟ .ε⎠⎝231ε.Нижняя граница сложности алгоритмов некоторых классов.Оптимальные алгоритмыПример.

Рассмотрим задачу поиска максимального элемента массива. Очевидно, что решитьэту задачу менее чем за (n − 1) сравнение нельзя.Определение. Пусть A — класс алгоритмов, решающих некоторую задачу. n — размервхода. Функция f (n) называется нижней границей сложности принадлежащих Aалгоритмов, если ∀A ∈ A ⇒ TA (n) ≥ f (n) ∀n .Если сложность зависит от нескольких параметров размеров входа n1 ,..., nk , то нижняяграница — функция нескольких переменных.Для рассмотренного выше примера (поиск максимума) f (n) = n − 1 .Какой именно класс A в определении нижней границы имеет большое значение.

Например,если имеется функция поиска максимума и сложность алгоритма измеряется в обращениях кэтой функции, то и нижняя граница будет иной.Рассмотрим алгоритмы сортировки. Такие алгоритмы можно изобразить в виде дерева:n = 2:1x1 < x2x1 , x20x2 , x1n = 3:x1 < x21x1 , x2 , x3x2 < x31x1 , x3 , x21000x1 < x3x2 , x1 , x30x3 , x1 , x2x3 < x11x3 , x2 , x11x3 < x20x2 , x3 , x1Если высота двоичного дерева h , то число листьев на нём ≤ 2 h (т.к. число листьев 2 hдостигается на полном двоичном дереве, т.е. дереве, у которого заполнены все уровни).Очевидно, что h в данном случае соответствует сложности алгоритма.

В дереве сортировкиn! листьев, откуда получаем нижнюю границу сложности для алгоритмов сортировки:2T ( n ) ≥ n! ⇒ T (n) ≥ ⎡log 2 n!⎤ .Вспомним алгоритм бинарного поиска: есть массив x1 < x2 < ... < xn и некоторое заданноечисло y, для которого требуется найти место в массиве, чтобы сохранилась упорядоченность.Для вставки y существует (n + 1) возможность: y ≤ x1 ; x1 < y ≤ x2 ; …; xn < y . Задачаалгоритма заключается в определении номера возможности. Опять же можно строить дерево,24но в данном случае листьев на дереве будет (n + 1) листьев, и оценка для сложности приметвид: T (n) ≥ ⎡log 2 (n + 1)⎤ .Вспомним алгоритм вычисления степени a n с помощью умножений. Каждый этапалгоритма может быть охарактеризован тем, какие степени мы имеем на текущий момент:a i1 ,..., a im и более того, какой максимальный порядок встречается в этом наборе. На каждомшаге максимальный порядок может увеличиться не более чем в 2 раза.

Определим на набореa i1 ,..., a im функциюλ = log 2 n − log 2 i123constгде i — максимум из i1 ,..., im . Тогда функция на каждом шаге может уменьшить своёзначение не более чем на 1. Очевидно, что в этих обозначениях алгоритм заканчивает работу,как только λ станет ≤ 0 . Отсюда получаем нижнюю границу сложности алгоритма: log 2 n .Определение.

Если в A ∃A : TA (n) является нижней границей сложности для A , то Aявляется оптимальным в этом классе и ∀B ∈ A ⇒ TB (n) ≥ TA (n) .Найти оптимальный алгоритм значит найти нижнюю границу для алгоритмов данногокласса и предъявить алгоритм с такой сложностью.Рассмотрим задачу: имеется массив, требуется найти и минимальный, и максимальный⎡ 3n ⎤элемент.

Покажем, что нижняя граница сложности составляет f (n) = ⎢ ⎥ − 2 и приведём⎢2⎥оптимальный алгоритм.Каждый этап произвольного алгоритма V, решающего эту задачу, характеризуетсяследующей четвёркой множеств элементов массива: ( A, B, C , D) , где A — множествоэлементов, не участвовавших в сравнениях; B — множество элементов, которые во всехсравнениях оказывались большими; C — множество элементов, которые во всех сравненияхоказывались меньшими; D — множество элементов, которые в некоторых сравнениях былибольше, а в других — меньше.

Начальная ситуация в ведённых обозначениях выглядит как(n, 0, 0, 0) , конечная — (0, 1, 1, n − 2) , т.е. множества B и C состоят из одного элемента,которые и будут максимальным и минимальным соответственно.3a + b + c − 2 , где a, b и c соответствуют числу элементов в2соответствующих множествах A, B и C. Возможны следующие сравнения исоответствующие изменения функции λ :( A, B, C , D)изменение λсравнение(a − 2, b + 1, c + 1, d )AA−113(a − 1, b, c + 1, d ) | (a − 1, b, c, d + 1)− |−AB2213(a − 1, b + 1, c, d ) | (a − 1, b, c, d + 1)− |−AC2211(a − 1, b + 1, c, d ) | (a − 1, b, c + 1, d )− |−AD22(a, b − 1, c, d + 1)BB−1(a, b − 1, c − 1, d + 2) | (a, b, c, d )−2 | 0BC(a, b − 1, c, d + 1) | (a, b, c, d )−1 | 0BDРассмотрим функцию λ (a, b, c) =25(a, b, c − 1, d + 1)(a, b, c − 1, d + 1) | (a, b, c, d )(a, b, c, d )CCCDDD−1−1 | 00Здесь AA означает сравнение элемента из A с элементом из A; AB — сравнение элемента из Aс элементом из B и т.д.В худшем случае шаг от шага λ уменьшается не более, чем на 1, откуда получаем нижнюю⎡ 3n ⎤границу сложности f (n) = ⎢ ⎥ − 2 .⎢2⎥Приведём оптимальный алгоритм, решающий поставленную задачу: изначально имеетсямассив из n элементов x1 ,..., xn .

Разобьём исходный массив на пары x1 , x2 ; x3 , x4 ; … В каждойпаре найдём минимум и максимум за одно сравнение. Тогда минимальные элементы из паробразуют множество m1 , m2 ,... , а максимальные — M 1 , M 2 ,... Среди m1 , m2 ,... найдёмминимальный, среди M 1 , M 2 ,... — максимальный.

Если на первом шаге был непарныйэлемент (n — нечётное), то на него потребуется ещё два сравнения с найденнымиминимумом и максимумом. В итоге на каждую пару тратится 3 сравнения.Надо добавить, что оптимальный алгоритм не обязан существовать. Например, врассматриваемом классе алгоритмов имеется всего 2 алгоритма, один из которых быстроработает для чётных n, второй — для нечётных.Оптимальные алгоритмы сортировки.Для построения оптимального алгоритма сортировки можно, конечно, построить всевозможные бинарные деревья с n! листьями, выбрать дерево с наименьшей высотой ипредъявить.Считалось, что алгоритм бинарными вставками является оптимальный.

Но для n = 5 емупонадобиться 8 сравнений, в то время как полученная выше нижняя граница даёт⎡log 2 n!⎤ = ⎡log 2 5!⎤ = 7 .⇒⇒⇒а)б)сравнений:233+25Очевидно, что для полного упорядочения потребуется ещё не более 2-х сравнений, в итогеполучим 7, т.е. алгоритм для сортировки массива длины 5, сложность которого равна 7,существует. Интересно, что уже для n = 12 оптимальный алгоритм потребует ⎡log 2 12!⎤ + 1сравнений.Бинарный алгоритм возведения в степень не является оптимальным. Оптимальным являетсяалгоритм, называемый схемой Горнера, который по заданным числам a0 , a1 , ..., an , xвычисляет значение выражения an x n + an−1 x n−1 + ...

+ a1 x + a0 и требует n умножений.Нужно отметить, что оптимальных алгоритмов человечество знает не много. Поэтомупонятие оптимальности хорошо было бы расширить.Определение. Асимптотической нижней границей сложности алгоритмов некоторого классаA называется такая функция f (n) , что ∀A ∈ A ⇒ TA (n) = Ω( f (n) ) .26Определение. Алгоритм называется асимптотически оптимальным (оптимальным попорядку сложности), если TA (n) является асимптотической нижней границей сложности и∀B ∈ A ⇒ TB (n) = Ω(TA (n) ) .Оптимальных по порядку сложности алгоритмов в определённом класс может бытьнесколько, но оптимальная асимптотическая сложность определена однозначно.Пусть A и B — оптимальные алгоритмы по порядку сложности.