С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 37
Текст из файла (страница 37)
Мы используем здесь то, что операции вычитанияи деления на 2 имеют сложность O(m), и то, что TAS (m) ¾ m по условию .Таким образом, если принимаются ограничения — для сложностей алгоритмов решения задачи S, то M ¶ S.§ . Линейная сводимостьПример .. Из формулы (.) нельзя сделать вывода, что задача построения транзитивно-рефлексивного замыкания графа с n вершинами (или, в другой терминологии, транзитивно-рефлексивногозамыкания булевой матрицы порядка n) линейно сводится к задаче умножения двух булевых матриц порядка n, так как само числоумножений матриц в этой формуле существенно зависит от n.
Номы покажем, что соответствующая линейная сводимость имеет место, если принять, что для любого из рассматриваемых алгоритмовумножения булевых матриц порядка n его сложность B(n) (примемэто упрощенное обозначение) удовлетворяет, хотя бы для всех достаточно больших n, условиям) B(1) = 1,) B(n) не убывает при возрастании n,) 4B(n) ¶ B(2n) ¶ 8B(n).Комментарий к условию . Неравенство B(2n) ¶ 8B(n) отсекаетте алгоритмы умножения булевых матриц, сложность которых растет быстрее чем n3 . Алгоритм должен построить n2 элементов матрицы-произведения, поэтому его сложность не может расти медленнеечем n2 , и в соответствии с этим в ограничения включается неравенство 4B(n) ¶ B(2n).Для булевой матрицы X порядка n будем, как и прежде, обозначать ее транзитивно-рефлексивное замыкание через X ∗ .Пусть G — ориентированный граф с n вершинами и C — его матрица смежности.
Предположим вначале, что n — четное число: n = 2l.Разобьем множество вершин V = {v1 , v2 , ..., v2l } графа G на два подмножества V1 = {v1 , v2 , ..., vl } и V2 = {vl +1 , vl +2 , ..., v2l }, а множество ребер графа G — на четыре подмножества E11 , E12 , E21 , E22 : начало каждого из ребер из множества E pq принадлежит Vp , а конец — Vq , гдеp, q ∈ {1, 2}. Если исходная матрица C представлена в блочном видеC11 C12,C21 C22где каждый блок — это матрица порядка l, то матрица C pq несет полную информацию о ребрах из множества E pq . Рассмотрим пути в графе G, соединяющие вершины из множества V1 .
Назовем ходом путьиз вершины в вершину этого множества, представляющий собой• либо продвижение по ребру, принадлежащему E11 ,• либо продвижение по ребру, принадлежащему E12 , за которым следует некоторый путь по ребрам из E22 и затем продвижение поребру, принадлежащему E21 .Глава . Сводимость∗Непосредственно видно, что (i, j)-элемент матрицы C11 ∨ (C12 ∧ C22∧ C21 )равен 1, если и только если существует ход, соединяющий вершиныvi , vj ∈ V1 . При этом ясно, что из vi можно добраться в vj (vi , vj ∈ V1 ) поребрам графа G, если и только если существует последовательность ходов, приводящая из vi в vj , т. е.
если и только если (i, j)-элемент матрицы∗(C11 ∨ (C12 ∧ C22∧ C21 ))∗равен 1. Обозначим эту матрицу F11 . Мы имеемF11 F12∗C =F21 F22для некоторых матриц F12 , F21 , F22 , при этом матрица Fpq , p, q ∈ {1, 2},несет информацию о существовании путей из вершин множества Vpв вершины множества Vq . Рассуждениями, сходными с приведеннымивыше, можно показать, что∗F12 = F11 ∧ C12 ∧ C22,∗F21 = C22 ∧ C21 ∧ F11 ,∗∗∗F22 = C22∨ (C22∧ C21 ∧ F11 ∧ C12 ∧ C22);эти выражения удобны для вычисления матрицы C ∗ : четыре матрицы Fp,q , p, q ∈ {1, 2}, можно найти, выполнив два построения транзитивно-рефлексивных замыканий, шесть умножений и два сложенияматриц порядка l:∗U = C22,V = C12 ∧ U,W = U ∧ C21 ,F11 = (C11 ∨ (V ∧ C21 ))∗ ,F12 = F11 ∧ V ,F21 = W ∧ F11 ,F22 = U ∨ (F21 ∧ V ).Мы указали рекурсивный переход от матриц порядка 2l к матрицампорядка l.
Учитывая, что C ∗ = C для матрицы первого порядка, мыполучаем алгоритм вычисления C ∗ для случаев, когда порядок n матрицы равен 2k , k ¾ 0. Пусть для умножения булевых матриц используется алгоритм со сложностью B(n), которая удовлетворяет условиям —, приведенным в начале этого примера. Для n = 2k мы имеем следующее соотношение, которому будет удовлетворять сложность§ . Линейная сводимостьT(n) полученного алгоритма построения транзитивно-рефлексивногозамыкания:¨0,если k = 0,kT(2 ) ¶(.)k −1k −12(k −1)2T(2 ) + 6B(2 ) + 2 · 2, если k > 0.В силу условия имеем B(2k−1 ) ¾ 4B(2k−2 ) при k ¾ 2. Дополнительноеиспользование условия дает нам B(22k−1 ) ¾ 22(k−1) при k ¾ 1.
Заменяя 22(k−1) во второй строке соотношения (.) на B(2k−1 ), получаем¨0,если k = 0,k(.)T(2 ) ¶k −1k −12T (2 ) + 8B(2 ), если k > 0.Докажем по индукции, чтоT(2k ) ¶ 4B(2k ),k = 0, 1, ...(.)Для k = 0 это неравенство очевидно, так как T(1) = 0, B(1) = 1. Пустьk > 0 и неравенство выполнено для k − 1. Тогда 2T (2k−1 ) ¶ 8B(2k−1 ), и,как следствие (.), мы получаем T(2k ) ¶ 16B(2k−1 ). В силу условия 1мы имеем B(2k−1 ) ¶ B(2k ), откуда следует (.).4Если n не есть число вида 2k , то от матрицы C переходим к матрицеC 0C′ =,0 Isпорядка 2k , взяв единичную матрицу I s некоторого порядка, меньшего чем порядок матрицы C.
Таким образом, порядок матрицы C ′меньше, чем 2n, т. е. 2k < 2n. Из (.) следует, чтоT(n) = T(2k ) ¶ 4B(2k ).Так как 2k < 2n и функция B(n) — неубывающая, получаем 4B(2k ) ¶¶ 4B(2n). ОтсюдаT (n) ¶ 4B(2n) ¶ 4 · 8 · B(n) = 32B(n)для всех n иT(n) = O(B(n)),(.)что и требовалось.Из сказанного следует, что если использовать для умножения квадратных булевых матриц алгоритм со сложностью, растущей медленнее, чем n3 , и удовлетворяющей условиям —, то можно строить транзитивно-рефлексивное замыкание со сложностью, растущей медленнее, чем сложность алгоритма Уоршелла (пример .).
Напомним, чтоГлава . Сводимостьалгоритм Штрассена умножения матриц, модифицированный для буe log2 7 ). Но для небольлева случая (пример .), имеет сложность O(nших значений n условия — здесь выполняться не будут. Однако соотношение (.) можно доказать при более слабых предположениях, чем использованные выше, и обсуждавшееся доказательство не потребует больших изменений. А именно, достаточно предположить, чтоB(n) удовлетворяет условиям — для n > n0 , где n0 — некоторое натуральное число (см.
задачу б). Получится оценка T(n) ¶ cB(n), гдеc зависит от B(n0 ), но эта зависимость не влияет на (.).Для нахождения транзитивно-рефлексивного замыкания ориентированного графа с n вершинами существует алгоритм, сложность коe log2 7 ).торого допускает оценку O(n2,82 ), или, более точно, оценку O(nКак показывает последний пример, если P ¶ Q, то прогресс в умении быстро решать задачу Q может в некоторых случаях обеспечитьпрогресс и в умении быстро решать задачу P. Но это не всегда так.Допустим, что n является нижней границей сложности для алгоритмов решения задачи Q и в то же время для задачи P имеется алгоритм решения со сложностью, меньшей n.
Согласно определению .мы имеем P ¶ Q, но наличие этой линейной сводимости ничего недает для продвижения в умении быстро решать задачу P.Отношение линейной сводимости, очевидно, рефлексивно. Еслине рассматривать упомянутых в определении . дополнительныхусловий, то это отношение будет транзитивным.
В тех случаях, когдатакие условия наложены, необходима осмотрительность: если для задач P, Q и R мы имеем P ¶ Q при некоторых условиях на сложностьалгоритмов решения Q, а также Q ¶ R при соответствующих условияхна сложность алгоритмов решения R, то чтобы на основании этогоутверждать, что P ¶ R, надо дополнительно установить, что сложности тех алгоритмов решения задачи Q, которые сопоставляются алгоритмам решения задачи R, удовлетворяют условиям, налагаемым насложности алгоритмов решения задачи Q при доказательстве отношения P ¶ Q. Это обстоятельство иногда безосновательно игнорируется.§ . Линейная сводимость и нижние границы сложностиНижеприведенная теорема является следствием определения ..Теорема ..
Пусть задачи P и Q таковы, что P ¶ Q. Пустьf (n) — асимптотическая нижняя граница сложности алгоритмов решения задачи P, и при этом соотношение P ¶ Q устанавливается без§ . Линейная сводимость и нижние границы сложностиналожения ограничений на сложность алгоритмов решения задачи Q.Тогда f (n) является асимптотической нижней границей сложностиалгоритмов решения задачи Q.Доказательство. Для каждого алгоритма AQ решения задачи Qнайдется такой алгоритм A P решения задачи P, для которого TAP (n) == O(TAQ (n)), или, эквивалентно, TAQ (n) = Ω(TAP (n)).
Но TAP (n) == Ω( f (n)), следовательно, TAQ (n) = Ω( f (n)).Если при соблюдении условия этого предложения для какого-тоалгоритма AQ решения задачи Q имеет место оценка TAQ (n) == O( f (n)), то этот алгоритм будет оптимальным по порядку сложности и TAQ (n) = Θ( f (n)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
