С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 30

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 30)

Итоговая сложность алгоритма допускает оценку O(m11 ). Заметим попутно, что в литературе по теории сложностиe f (m)) (Oe называется «O мягкое»),часто используются оценки вида O(Глава . Битовая сложностьза таким обозначением скрывается O( f (m) logd m), где d — положительное число, значение которого не уточняется. Авторы показывают,e 21/2 ), укачто битовая сложность их алгоритма допускает оценку O(mзывая при этом, что если верны некоторые известные в теории чиселгипотезы (для которых имеются серьезные основания полагать, чтоони верны), то можно взять r = O(m2 ), и в этом случае сложностьe 6 ).алгоритма в целом есть O(mНа этом мы завершим разговор об алгоритме AKS, добавив лишько всему сказанному, что, например, в криптографии практикуютсявероятностные (типа Монте-Карло) алгоритмы распознавания простоты, имеющие меньшую сложность, но не исключающие появления, хоть и с малой вероятностью, неверного ответа.

В нашем курсетакого рода алгоритмы не рассматриваются  .§ . Булева арифметикаСложность булевых вычислений как сложность по числу булевых операций может рассматриваться как алгебраическая сложность. Но работа с булевыми величинами является фактически работой с битами, и сложность по числу булевых операций в этом смысле совпадает с битовой сложностью. Таким образом, для алгоритмов булевойарифметики алгебраическая сложность по числу булевых операцийи битовая сложность — это одно и то же. Аналогично дело обстоити с пространственной булевой (= битовой) сложностью.Пример .. Пусть дан ориентированный граф G = (V , E), n = | V |.Пусть C = (cij ) — булева матрица смежности графа G: cij = 1, еслии только если i-я вершина соединена ребром с j-й, i, j = 1, 2, ..., n.Требуется построить для G его матрицу связности D = (dij ): dij = 1,если и только если i = j или i-я вершина соединена путем из одногоили более ребер с j-й, i, j = 1, 2, ..., n.

Если рассматривать G как графнекоторого бинарного отношения на множестве из n элементов, тозадачу можно интерпретировать как задачу построения транзитивно-рефлексивного замыкания данного бинарного отношения. Соответственно, граф, для которого D является матрицей смежности, называют транзитивно-рефлексивным замыканием графа G, а саму матрицу D — транзитивно-рефлексивным замыканием матрицы C.

Дляматрицы D используется обозначение C ∗ . На рис.  показан ориентированный граф и его транзитивно-рефлексивное замыкание. СоотПо поводу этих алгоритмов распознавания простоты числа см. [, гл. ] и [,гл. ].§ . Булева арифметика43а)4312б)1525Рис. . а) Ориентированный граф; б) его транзитивно-рефлексивное замыкание.и C ∗ выглядят следующим образом1 1 1 10 11 01 1 1 1. , C∗ = 0 11 1 1 10 0 0 10 0ветствующие матрицы C0 10 1C =1 00 0Нам понадобятся произведения булевых матриц, которые определяются как обычно: например, произведение F квадратных матрицA и B порядка n определяется формулойfij =n_(aik ∧ bkj ),i, j = 1, 2, ..., n.k =1Элемент с индексами i, j для краткости будем называть (i, j)-элементом матрицы.Легко видеть, что C 2 = C ∧ C — это матрица, для которой (i, j)-элемент равен 1, если и только если i-я вершина соединена с j-й путемдлины 2 (т.

е. состоящим из двух ребер). Аналогично, C k — матрица,для которой (i, j)-элемент равен 1, если и только если i-я вершина соединена с j-й путем длины k. Пусть I — матрица, для которой(i, j)-элемент равен 1, если и только если i = j. ТогдаC ∗ = I ∨ C ∨ C 2 ∨ ... ∨ C n−1 .Индукцией по k несложно доказать, что для любой квадратной булевой матрицы C и натурального k выполненоI ∨ C ∨ C 2 ∨ ... ∨ C k = (I ∨ C)k .(.)C ∗ = (I ∨ C)n−1 .(.)Это дает намГлава . Битовая сложностьТривиальный способ умножения булевых (n × n)-матрицΘ(n3 ) битовых операций. Если используется именно этотто оценка числа операций для формулы (.) есть Θ(n4 ).нение бинарного алгоритма (пример .) для возведения вбулевой матрицы C позволяет перейти к оценкеΘ(n3 log n).требуетспособ,Приместепень(.)Если нежелательно связывать основанный на формуле (.) алгоритм построения транзитивно-рефлексивного замыкания с конкретным способом умножения матриц, то верхнюю оценку числа битовыхопераций можно записать какn + B(n)(λ(n) + λ∗ (n) − 2),(.)где B(n) — сложность используемого алгоритма умножения булевых(n × n)-матриц; слагаемое n отражает расход на сложение с матрицей I.Рассмотренный пример высвечивает связь задачи построениятранзитивно-рефлексивного замыкания ориентированного графа с задачей умножения булевых матриц.

Эта связь оказывается очень тесной, о чем мы еще будем говорить в § .В следующем примере задача построения транзитивно-рефлексивного замыкания решается без использования умножения булевыхматриц.Пример .. Исследуем сложность алгоритма С. Уоршелла, предназначенного для построения матрицы C ∗ . В процессе примененияэтого алгоритма матрица C ∗ строится за n = | V | шагов, после k-гошага получается матрица D (k) = (dij(k)), и dij(k) = 1, если и только еслиi-я вершина соединена таким путем с j-й, номера всех промежуточных вершин которого не выходят за пределы множества {1, 2, ..., k}.Вначале полагаем D (0) = I ∨ C.

Затем для каждого k = 1, 2, ..., n находим D (k) :(k −1)(k −1)dij(k) = dij(k−1) ∨ (dik∧ dkj).(.)После этого C ∗ = D (n) .Формула (.) отражает то, что путь из i-й вершины в j-ю, всепромежуточные вершины которого принадлежат {1, 2, ..., k}, существует, если и только если реализуется хотя бы одна из следующихвозможностей:• имеется путь из i-й вершины в j-ю, все промежуточные вершиныкоторого принадлежат {1, 2, ..., k − 1};§ . Булева арифметика• имеются пути из i-й вершины в k-ю и из k-й в j-ю, все промежуточные вершины которых принадлежат {1, 2, ..., k − 1}.На вычисление D (0) уходит n битовых операций, вычисление каждой из матриц D (k) , 1 ¶ k ¶ n, требует 2n2 операций.

Итого, требуется2n3 + n операций.Алгоритм Уоршелла вычисляет матрицу C ∗ , т. е. строит транзитивно-рефлексивное замыкание ориентированного графа G с n вершинами, заданного матрицей смежности, затрачивая 2n3 + n битовыхопераций.Алгоритм Уоршелла можно легко реализовать так, что хранитьсяв памяти будут только D (k−1) и D (k) . Но на самом деле алгоритм Уоршелла позволяет производить все вычисления, расходуя всего n2 битов под хранение матричных элементов. Если мы вычислим D = I ∨ C,а затем n раз обновим матрицу D (каждый раз всю целиком, неоставляя незатронутых элементов), используя на k-м этапе обновления матрицы D присваиванияdij := dij ∨ (dik ∧ dkj ),k = 1, 2, ...

n, то получим искомую матрицу связности. В самом деле,индукцией по k можно доказать, что после k-го этапа обновления получаем матрицу, равную D (k) , при этом индуктивный переход от k − 1к k основывается на том, что имеют место очевидные соотношения(k)(k −1)dik= dik,(k)(k −1)dkj= dkj,k = 1, 2, ..., n, т. е. при обновлении элемента dij на k-м этапе не имеет никакого значения, был ли уже обновлен какой-то из элементовdik , dkj или нет.Если строить матрицу C ∗ на месте исходной матрицы C, то алгоритм можно изобразить так:for l = 1 to n do cll := 1 od;for k = 1 to n dofor i = 1 to n dofor j = 1 to n doodcij := cij ∨ (cik ∧ ckj )ododПодводя итог рассмотрению алгоритма Уоршелла, заметим, что,как и алгоритм Евклида в расширенной версии, он дает довольноГлава . Битовая сложностьредкий пример, когда низкие временные затраты сочетаются с малымрасходом памяти.Алгоритм Уоршелла построения замыкания ориентированногографа имеет битовую временную сложность 2n3 + n, где n = | V | — число вершин графа.

Пространственная сложность этого алгоритмаограничена константой.При рассмотрении | V |, | E | в качестве двух параметров размеравхода сказанное сохраняет силу, так как затраты алгоритма Уоршеллане зависят от числа ребер заданного входного графа.Задачи. Исследовать битовую сложность вычисления величины 1 ++ 2 + ... + n последовательными сложениями. Размером входа считатьбитовую длину m целого числа n.. Для временной битовой сложности «сверхнаивного» умножения (пример .) при использовании параметров m1 , m2 верна оценкасверху O(2max{m1 ,m2 } max{m1 , m2 }), а оценка Θ(2max{m1 ,m2 } max{m1 , m2 })неверна.Указание. Неверна оценка Ω(2max{m1 ,m2 } max{m1 , m2 }): она противоречилабы оценке O(2m2 m1 ), так как для любого N > 0 существуют m1 , m2 > N такие,что m1 = 2m2 ..

Определение чисел Фибоначчи, данное в § , позволяет вычислить Fn , выполнив n − 1 сложение. Битовая сложность этого алгоритма допускает оценку O(n2 ) при рассмотрении n в качестве размера входа.. Обосновать использованный в доказательстве предложения∗∗. переход от оценки TND(m1 , m2 ) = O((m1 − m2 + 1)(m2 + 1)) к∗∗TND (m1 , m2 ) = O((m1 − m2 + 1)m2 ).. Можно ли усилить предложение ., заменив приведенныетам оценки O(log a log b), O(log2 a) на Θ(log a log b), Θ(log2 a)?. Рассмотрим m = λ(n) в качестве размера входа алгоритма вычисления факториала (пример .). Верна ли для соответствующейвременной битовой сложности оценка O(2m m)?.

Характеристики

Список файлов лекций