Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 38
Текст из файла (страница 38)
Линейная сводимостьНиже в сопоставляемых друг с другом вычислительных задачах подразумеваются преобразования каких-то математических объектов,представляемых одинаково для всех задач, участвующих в сопоставлении. Размер входа для алгоритмов решения рассматриваемых задачтоже должен определяться единообразно. При сравнительном исследовании задач затраты на выполнение вычислений измеряются количеством операций из одного и того же набора (например, арифметических операций, битовых операций и т. д.).Определение .. Пусть P и Q — две вычислительные задачи.Если любому алгоритму AQ решения задачи Q можно сопоставитьтакой алгоритм A P решения задачи P, чтоTAP (n) = O(TAQ (n)),(.)то говорят, что задача P линейно сводится к задаче Q, и пишут P ¶ Q.В специально оговариваемых случаях утверждение P ¶ Q предполагает, что рассматриваются лишь такие алгоритмы AQ , сложности которых удовлетворяют некоторым фиксированным условиям.Слово «линейно» в этом определении означает лишь то, что сложность получаемого алгоритма A P не является, скажем, квадратом, кубом и т.
д. сложности алгоритма AQ . Возможное присутствие условий(ограничений) на сложности алгоритмов решения задачи Q облегчает или просто делает возможным доказательство (.). В то же время, предполагается, что эти ограничения отсекают нерациональныеалгоритмы; тогда смысл отношения P ¶ Q состоит в том, что каж-Глава . Сводимостьдому приемлемому («хорошему») алгоритму решения задачи Q мыможем сопоставить алгоритм решения задачи P такой, что выполнено (.).Пример .. Будем рассматривать задачи умножения M и возведения в квадрат S неотрицательных целых чисел, заданных в двоичной системе, считая размером входа в первой задаче максимальнуюиз битовых длин чисел n1 , n2 , а во второй — битовую длину данногочисла n (будем обозначать этот размер через m), в качестве затратбудем рассматривать битовые затраты.Из равенства n2 = n · n следует, что S ¶ M, так как это равенстводает требуемый определением . алгоритм. Дает ли равенствоn1 · n2 =(n1 + n2 )2 − n21 − n222(.)основание считать, что M ¶ S? Битовая длина числа n1 + n2 можетоказаться равной m + 1.
Если бы для возведения в квадрат использовался некоторый чрезвычайно нерациональный алгоритм, имеющий, скажем, сложность m!, то соответствующий алгоритм умножения имел бы сложность порядка (m + 1)!. Легко видеть, что равенство(m + 1)! = O(m!) места не имеет. Можно пытаться определить умножение через возведение в квадрат как-то иначе, но можно и не отказываться от формулы (.): при установлении линейной сводимостиобычно считается, что сложность любого приемлемого алгоритма выполнения какой-либо мультипликативной арифметической операции(умножения, возведения в квадрат, деления и т.
д.) удовлетворяет, хотя бы для всех достаточно больших m, условиям) T(m) ¾ m,) T(m) не убывает при возрастании m,) T(2m) ¶ 4T(m)(условие отсекает алгоритмы умножения, сложность которых растетбыстрее чем m2 ). Приняв, что сложность алгоритма AS удовлетворяетэтим условиям, мы имеемTAS (m + 1) ¶ TAS (2m) ¶ 4TAS (m),что дает TAM (m) = O(TAS (m)) для описанного с помощью (.) алгоритма умножения. Мы используем здесь то, что операции вычитанияи деления на 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.Отношение линейной сводимости, очевидно, рефлексивно. Еслине рассматривать упомянутых в определении . дополнительныхусловий, то это отношение будет транзитивным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
