С.А. Абрамов - Вычислительная сложность алгоритмов (1123766)
Текст из файла
Московский Государственный Университетимени М. В. ЛомоносоваФакультет Вычислительной Математики и КибернетикиКафедра Алгоритмических ЯзыковНЕ ЯВЛЯЕТСЯ ОФИЦИАЛЬНЫМ УЧЕБНЫМ ПОСОБИЕМВычислительная сложностьалгоритмов(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) — финально неубывающая.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
