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

Московский Государственный Университетимени М. В. ЛомоносоваФакультет Вычислительной Математики и КибернетикиКафедра Алгоритмических ЯзыковНЕ ЯВЛЯЕТСЯ ОФИЦИАЛЬНЫМ УЧЕБНЫМ ПОСОБИЕМВычислительная сложностьалгоритмов(V семестр)лектор — профессор С. А. Абрамов(составлено по конспекту лекций за осенний семестр 2005/06 учебного года)Москва 2005СодержаниеСложность алгоритмов как функций числовых аргументов .........................................................3Сложность в среднем.........................................................................................................................9Нижняя граница сложности алгоритмов некоторых классов. Оптимальные алгоритмы.........24Битовая сложность...........................................................................................................................30Об одном классе рекуррентных соотношений («разделяй и властвуй»)....................................37Сводимость .......................................................................................................................................48Задачи................................................................................................................................................562Сложность алгоритмов как функций числовых аргументовА — алгоритм: на вход x, результат — y.C AT (x) — временные затраты (цена)C AS (x) — пространственные затраты (по памяти)x — размер входа: x ≥ 0⎣x ⎦ — пол: округление в меньшую сторону⎡x ⎤ — потолок: округление в большую сторонуПримеры⎣3,14⎦ = 3 ;⎣− 3,14⎦ = −4⎡− 3,14⎤ = −3 ; ⎡3,14⎤ = 4Рассмотрим следующие алгоритмы:1.

(MM) Перемножение 2-х квадратных матриц порядка n: требуется n3 умножений.2. (TD) Проверка на простоту числа n — пробные деления на 2, 3, …,1 до⎣ n ⎦ − 1 делений.⎣ n ⎦ : требуется от3. (I) Сортировка простыми вставками массива из n элементов: требуется от n − 1 доn(n − 1)сравнений.2Определение. Временной сложностью (сложностью в худшем случае по времени) алгоритмаA называется функция от размера входа n следующего вида: T A (n) = max C AT ( x) .x =nОпределение. Пространственной сложностью (сложностью в худшем случае по памяти)алгоритма A называется функция от размера входа n следующего вида: S A (n) = max C AS ( x) .x =nЗамечание. Если алгоритм A представляет собой суперпозицию двух алгоритмов U и V:A = U ⋅ V , то вообще говоря, T A (n) ≠ TU (n) + TV (n) .Примеры.TMM (n) = n 3 ; TI (n) =n(n − 1); TTD (n) ≤2⎣ n ⎦−1Рассмотрим TTD (n) при конкретных значениях n:nTTD (n)1112112111391141115411611172118111961201Такое поведение сложности связано с неверным выбором размера входа.S TD (n) = O(1) ; S MM (n) = n 2 + O(1)Рассмотрим детальнее алгоритм сортировки простыми вставками (I).

Имеется массив из nэлементов: x1 , x 2 ,..., x n . Считая на i-м шаге, что первые (i − 1) элементов упорядочены и3нужно поставить (i + 1) -й элемент на место. Для этого представляются 2 возможности: 1)пока (i + 1) -й элемент больше соседнего левого, менять их местами; 2) начиная с первогоэлемента и до i-го, сравнивать каждый элемент с (i + 1) -м, для определения правильногоместа (i + 1) -го элемента, после чего начать перестановки, аналогичные пункту 1, чтобы(i + 1) -й элемент встал на нужное место. Оказывается, что сложности в этих двух случаях(n − 1)(n + 2)будут различны: TI1 (n) = n(n − 1) ; TI1 (n) =.

Тем не менее TI (n) = O(n 2 ) , но22nT I 1 ( n ) = n 2 + O ( n ) , а TI 2 ( n ) =+ O ( n) .2Определение. Функции f (n) и g (n) являются функциями одного порядка, если найдутсятакие числа c1 , c2 > 0 и такое N > 0 , что ∀n > N верно c1 g (n) < f (n) < c2 g (n) .Обозначение:f (n) g (n); f (n) = Θ g (n)Пример. TI (n) = Θ(n)Замечание. Ограничение ∀n > N в определении не существенно и от него можно отказаться,рассматривая ∀n > 0 . Действительно, пусть условие c1 g (n) < f (n) < c2 g (n) выполняетсядля всех n, больших некоторого N. Обозначимm = min1≤n≤ NM = max1≤ n≤ Nf ( n), c1′ = min{c1 , m}g ( n)f ( n), c2′ = min{c2 , M } .g ( n)Тогда для таких c1′ и c′2 будет верно c1′ g (n) < f (n) < c2′ g (n) для всех n > 0 .Определение. f (n) = Ω( g (n) ) ⇔ ∃c, N > 0 : f (n) > c g (n) , ∀n > N .Определение.

Оценка f (n) = O( g (n) ) называется точной, если можно выбратьподпоследовательность {nk } такую, что для функций ϕ (k ) = f (nk ) и ψ (k ) = g (nk ) выполненоϕ (k ) = Ω(ψ (k ) ) или ϕ (k ) = Θ(ψ (k ) ) .Определение. Оценка f (n) = O( g (n) ) называется точной, если f (n) = O (g (n) ) верно, аf (n) = o(g (n) ) — не верно.Определение. Функция f (n) , определённая для достаточно больших n, называетсяфункцией, определённой финально.Рассмотрим алгоритм построения пересечения 2-х выпуклых многоугольников (алгоритмШеймоса (SH)).

Имеются два выпуклых многоугольника, заданные координатами своихвершин на плоскости: P1 , P2 , ... , Pl и Q1 , Q2 , ... , Qm . Упорядочим массивы вершин повозрастанию x. Для этого воспользуемся выпуклостью многоугольников. Найдем вершину сминимальной координатой x — в упорядоченном массиве она будет первой. Далее выбираемвершину, смежную с найденной и имеющую минимальную координату x — она будетвторой. Далее рассматриваются вершины, смежные с уже упорядоченными, но еще нерассмотренными: таких вершин не больше двух. Среди них выбираем ту, у которой меньшаякоордината x и добавляем в конец формируемого упорядоченного массива.

Процедураповторяется до тех пор, пока все вершины не будут рассмотрены алгоритмом и упорядочены.4Используя указанный алгоритм можно упорядочить массив вершин многоугольника P,выполнив ≤ c0l операций сравнения. Массив вершин многоугольника Q тем же алгоритмомупорядочивается за ≤ c0 m операций сравнения. Далее «сольём» полученные два массива,формируя новый массив длинной l + m , выбирая на каждом шаге минимальный из первыхнерассмотренных элементов массивов. Для этого потребуется ≤ c1 (l + m) операцийсравнения.ya1 a2 a3a4...ai ai+1 ...xal+mИтоговая сложность не превзойдёт c2 (l + m) . Для каждой полосы ai ai+1 строим пересечениедвух трапеций (в некоторых случаях трапеция вырождается в треугольник). Затемобъединяем пересечения и получаем требуемый результат, причём количество необходимыхопераций не превзойдёт c3 (l + m) .

В результате получаем оценки:l + m < CHS ( P, Q) < c(l + m)Если за размер входа взять величину r = l + m , тогда не трудно видеть, что TSH (r ) = Θ(r ) .Для размера входа s = max{m, l} имеем:′ ( s ) = Θ( s )s < m + l ≤ 2s ⇒ s ≤ CSH ( P, Q) ≤ 2cs ⇒ TSHЕсли рассматривать функцию сложности как функцию двух аргументов l и m, то не трудно′′ (l , m) = Θ(l + m) .видеть, что TSHОпределение.f (n1 , n2 ) = Θ( g (n1 , n2 ) ) ⇔ ∃c1 , c2 , N > 0такие,что∀n1 , n2 > Nверноc1 g (n1 , n2 ) ≤ f (n1 , n2 ) ≤ c2 g (n1 , n2 ) .Пусть G = (V , E ) — ориентированный граф. Вояжем в графе G назовем путь,удовлетворяющий 3 условиям: 1) он начинается в какой-то вершине графа G; 2) не проходитпо одной дуге дважды и 3) заканчивается в вершине, откуда нет путей.Вояж не обязательно охватывает все дуги графа.Пример.435126Вояж: (1, 2, 2, 3, 1, 4).57Рассмотрим алгоритм нахождения вояжа в графе.

Для этого сопоставим с графомквадратную матрицу, порядок которой совпадает с числом вершин в графе. Элементыматрицы aij показывают, сколькими ребрами соединяются вершины i и j. Для графа изпримера матрица выглядит следующим образом:⎡0⎢0⎢⎢1⎢⎢0⎢0⎢⎢0⎢0⎣110000001000001010000000001000001000⎤0⎥⎥0⎥⎥0⎥0⎥⎥0⎥0⎥⎦Алгоритм заключается в следующем: начинаем с любого ненулевого элемента матрицы aij,получаем начальную вершину вояжа i — строка матрицы с выбранным элементом.

Далее,так как элемент матрицы отличен от нуля, существует путь из этой вершины в вершину,соответствующую номеру столбца матрицы j. Полученная вершина будет второй в искомомвояже. Для продолжения алгоритма нужно уменьшить на единицу текущий элемент матрицыаij и перейти к рассмотрению строки j матрицы.

Если эта строка не содержит отличных отнуля элементов, то построение вояжа окончено, так как из текущей вершины нет путей. Еслинайдётся хотя бы один отличный от нуля элемент ajk, то в вояж добавляется вершина k,элемент ajk уменьшается на единицу и построение вояжа продолжается поиском ненулевогоэлемента в строке k.Рассмотрим сложность такого алгоритма. Не трудно видеть, что для заданного числа вершинсуществуют графы в виде «кольца» и «цветка»:«кольцо»«цветок»на которых будет достигаться максимальное число операций. Матрицы для таких графовимеют следующий вид:⎡0⎢0⎢⎢...⎢⎢0⎢0⎢⎢⎣ 110...00001...000..................00...1000⎤0 ⎥⎥...⎥⎥0⎥1⎥⎥0 ⎥⎦[n]для «цветка»,где n — число дуг в графедля «кольца»Для «кольца» с n вершинами получаем сложность: 2 + 3 + ...

+ n + 1 =T(E ) = c E .26n(n + 1), тем самым2Другой алгоритм для поиска вояжа основан на представлении графа в виде набора вершин,за каждой из которых закреплён список вершин, куда идут дуги из данной. Для графа изпримера это представление имеет вид:a1 = (2,4); a2 = (2,3); a3 = (1,4); a4 = ( ); a5 = (6); a6 = (5); a7 = ( )Для «кольца» имеем следующее представление:a1 = (2); a2 = (3); a3 = (4); …; a V −1 = (V ); a V = (1)Алгоритм для поиска вояжа по такому представлению приведём на псевдокоде:l := cons(v, nil); i := v;while not null(ai) doi := car(ai);l := cons(i, l);ai := cdr(ai);odгдеcar — первый элемент списка;cdr — конец списка;cons — вставка.Не трудно видеть, что сложность представленного алгоритма составляет c E , причёмT ( E ) = Θ( E ) , так как для любого числа рёбер E существует граф в виде «цветка».Битовая длина числа как размер входа.Рассмотрим функцию ν (n) , определённую следующим образом:⎧1, если n = 0⎩⎣log 2 n ⎦ + 1, если n > 0ν ( n) = ⎨Определение.

ν (n) называется битовой длиной n.Рассмотрим сложность алгоритма пробных делений (TD), взяв в качестве размера входабитовую длину n (сложность, для которой в качестве размера входа выбрана битовая n,будем обозначать TA* ).*(m = ν (n) ) :TTDmnn̂*TTD (m)22-33134-75148-15132516-31314632-63596764-12712710где n̂ — некоторое конкретное число из указанного интервала, на котором достигаетсямаксимум делений. Таких чисел в конкретном интервале может быть больше одного(например, для интервала 64-127 число 121 тоже требует 10 делений для определенияпростоты).

Как видно из приведённой таблице, сложность алгоритма пробных деленийрастёт вместе с ростом величины размера входа, что даёт возможность вычислить еёасимптотику.Для этого используем постулат Бертрана, который приведём без доказательства.Теорема (постулат Бертрана). ∀N > 1 в интервале ( N , 2 N ) найдётся простое число.7⎛ m⎞*(m = ν (n) ) = Θ⎜⎜ 2 2 ⎟⎟ (см. задачу 6).Используя это утверждение, легко показать, что TTD⎝ ⎠Лемма 1. Пусть f (x) — финально неубывающая.