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

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

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

ПолучаемTKM (m) = O(mlog2 3 ),при этом log2 3 = 1,58...(.)Глава . Рекуррентные соотношения и сложность алгоритмовДля m > 1 мы имеемTKM (m) > G(m),(.)где функция G натурального аргумента такова, что G(m) = G(2⌈log2 m⌉ )для всех m ∈ N+ и¨1,если k = 0,kG(2 ) =3G(2k−1 ), если k > 0,откуда TKM (m) = Ω(mlog2 3 ) по предложению .. Вместе с (.) этодаетTKM (m) = Θ(mlog2 3 ).(.)При использовании m, равного максимальной из битовых длин двухданных чисел a, b ∈ N+ , в качестве размера входа битовая сложностьумножения Карацубы допускает оценкуTKM (m) = Θ(mlog2 3 ),при том, что TNM = Θ(m2 ) — оценка битовой сложности наивногоумножения  .Стратегия добавления нулей особенно характерна для исследований, в которых главной целью служит преодоление некоторого сложностного барьера; последнее было и остается важным стимулом развития теории сложности.Пример ..

Алгоритм Штрассена умножения двух квадратныхчисловых матриц A и B порядка n, являющегося степенью двойки,основан на том, что если n = 2l иA11 A12B11 B12A=, B=,A21 A22B21 B22где все Aij , Bij — квадратные матрицы порядка l, то матрицуC11 C12C = AB =C21 C22можно получить, выполнив семь умножений квадратных матриц порядка l (при том, что потребовалось бы восемь таких умножений приИстория создания алгоритма Карацубы и публикации о нем в  г.

сообщения [] увлекательно рассказана в статье [] самого А. А. Карацубы; особенно богатяркими историческими деталями раздел  этой статьи.§ . Добавление нулейиспользовании простейшего алгоритма, основанного на определениипроизведения матриц):X1 = (A11 + A22 )(B11 + B22 ),X2 = (A21 + A22 )B11 ,X3 = A11 (B12 − B22 ),X4 = A22 (B21 − B11 ),X5 = (A11 + A12 )B22 ,X6 = (A21 − A11 )(B11 + B12 ),X7 = (A12 − A22 )(B21 + B22 ),далее используются только аддитивные операции:C11 = X1 + X4 − X5 + X7 ,C21 = X2 + X4 ,C12 = X3 + X5 ,C22 = X1 + X3 − X2 + X6 .В правильности этого можно убедиться прямой проверкой.Равенство n = 2k создает возможность для рекурсивного применения алгоритма.

Алгоритм Штрассена будем обозначать начальнымибуквами St фамилии его автора.В приведенных формулах использовано восемнадцать сложенийматриц порядка l. Сложение двух матриц порядка l требует l 2 сложений чисел. В предположении, что n = 2k , k ∈ N, имеем для общегочисла операций — сложений и умножений чисел:(1, если n = 1, 2(.)TSt (n) =nn+ 18, если n > 1.7TSt22+Если n ∈ N произвольно, то вначале к матрицам A и B добавляются нулевые строки и столбцы (см.

(.)) так, чтобы порядки матриц стали равными 2⌈log2 n⌉ , а затем применяется описанный рекурсивный алгоритм. Рассматривая равенство (.) как систему двухнеравенств со знаками ¶ и ¾ и применяя теоремы . и ., получаем следующий результат.Сложность TSt (n) по числу арифметических операций алгоритмаШтрассена перемножения двух числовых матриц порядка n допускаетоценку TSt (n) = Θ(nlog2 7 ), в то время как алгоритм, непосредственноследующий из определения произведения матриц, имеет сложностьΘ(n3 ) (при этом log2 7 = 2,81...).Что касается булевых матриц, то алгоритм Штрассена не можетбыть непосредственно применен для их умножения по той, например, причине, что этим алгоритмом используется вычитание, для которого нет аналога в булевой арифметике.

Но матрицы A и B порядка n, состоящие из нулей и единиц, можно перемножить какГлава . Рекуррентные соотношения и сложность алгоритмовцелочисленные. Каждый элемент такого произведения не превосходит n, он равен нулю, если и только если соответствующий элемент произведения булевых матриц равен нулю. Для того, чтобыв процессе применения алгоритма Штрассена к целочисленным матрицам не возникало больших промежуточных значений, здесь можно все вычисления проводить по модулю n + 1, т.

е. проводить вычисления не в кольце Z, а в кольце Zn+1 . Если M(n) — некоторая верхняя граница для числа битовых операций, затрачиваемыхпри выполнении одной операции сложения, вычитания или умножения в Zn+1 , то сложность модифицированного таким способом алгоритма Штрассена будет допускать оценку O(nlog2 7 M(n)). Наивноеумножение в Zn+1 дает M(n) = O(log2 n). Таким образом, M(n) растет очень медленно в сравнении с остальными затратами. Так какlog2 7 = 2,81...

, мы можем использовать для сложности алгоритмаШтрассена, модифицированного на булев случай, например, оценкуe log2 7 ), — смысл «O мягкого» объяснялся в конO(n2,82 ) или оценку O(nце § .Применение алгоритма Штрассена и арифметики по модулю n + 1дает алгоритм умножения двух булевых матриц порядка n, битоваяe log2 7 ) и O(n2,82 ).сложность которого допускает оценки O(nМы ограничились рассмотрением применения стратегии «разделяй и властвуй» для случая, когда в результате этапа разделения возникают две задачи, и каждый из размеров входа примерно вдвоеменьше изначального размера. Иногда разделение приводит к треми более задачам.В  г. А. Л.

Тоом обобщил идею умножения Карацубы  . Пустьs — большее единицы целое. Предполагая, что битовая длина m каждого из сомножителей имеет вид sk , k ∈ N, последовательность двоичных цифр каждого из сомножителей можно разбить на s групп поsk−1 цифр. Тоом показал, что умножение исходных чисел сводитсяк 2s − 1 умножениям чисел битовой длины sk−1 (в умножении Карацубы s = 2, 2s − 1 = 3), остальные затраты — сложения, сдвиги — будутограничены функцией cm, где c — зависящая от выбора s константа.Здесь этап разделения приводит к 2s − 1 задачам. Для умножения Тоома (TM) неравенство(1,если m = 1,(s) (.)TTM (m) ¶(s) m+ cm, если m > 1,(2s − 1)TTMsСм.

[], [].§ . Добавление нулейвыполненное в случае m = sk , k ∈ N, и равенство(s)(s) ⌈logs m⌉TTM(m) = TTM(s),(s)выполненное при произвольном m ∈ N+ , приводят к оценке TTM(m) == O(mlogs (2s−1) ) для битовой сложности алгоритма, использующегоразбиение на s частей. Может быть также показано, что(s)TTM(m) = Θ(mlogs (2s−1) ).(.)Очевидно,11= 1 + logs 2 + logs 1 −.logs (2s − 1) = logs 2s 1 −2s2sОтсюдаlim logs (2s − 1) = 1.s→∞Это означает, что для любого ǫ > 0 можно найти целое s ¾ 2 такое, чтоумножение Тоома с разделением на s частей (битовая длина числапредполагается равной sk , k ∈ N) будет иметь битовую сложность, допускающую оценку Θ(m1+δ ) при некотором δ таком, что 0 < δ ¶ ǫ ; разумеется, для битовой сложности этого алгоритма справедлива оценка O(m1+ǫ ).Скажем коротко об основной идее алгоритма Тоома, приводящейк неравенству (.).

Если, как предполагалось, битовая длина каждого из сомножителей a, b есть sk , k ∈ N, то последовательность двоичных цифр каждого из сомножителей a, b можно разбить на s групппо sk−1 цифр:a s−1 , ..., a1 , a0 ; bs−1 , ..., b1 , b0 .Сами сомножители a, b суть значения полиномовA(x) = a s−1 x s−1 + ... + a1 x + a0 ,B(x) = bs−1 x s−1 + ... + b1 x + b0k−1в точке x0 = 2s . Полином C(x), равный произведению A(x)B(x), естьполином степени не выше чем 2s − 2 (мы не утверждаем, что этастепень равна 2s − 2, так как возможно, что к изначально заданнымцелочисленным сомножителям спереди дописывались нули), и достаточно знать значения C(x) в 2s − 1 точках (узлах интерполяции) длятого, чтобы затем, например, с помощью интерполяционной формулы Лагранжа найти значениеC(2sk−1),(.)Глава .

Рекуррентные соотношения и сложность алгоритмовравное ab. Тоом показал, что если в качестве узлов интерполяцииx1 , x2 , ..., x2s−1 взять числа−(s − 1), −(s − 2), ..., −1, 0, 1, ..., s − 2, s − 1,рекурсивно с помощью рассматриваемого алгоритма найтиA(xi ),B(xi ), C(xi ) = A(xi )B(xi ),i = 1, 2, ..., 2s − 1,и затем, пользуясь интерполяционной формулой Лагранжа, найтизначение (.), то это приведет к (.), (.). Такое использование интерполяции заключает в себе требуемое обобщение алгоритмаКарацубы.В  г. Шенхаге и Штрассен, основываясь на идее Тоома использования интерполяции полиномов в алгоритмах умножения целыхчисел, получили алгоритм умножения, битовая сложность которогодопускает оценку O(m log m log log m), мы уже упоминали этот алгоритм в § .

Функция m log m log log m растет медленнее, чем m1+δпри любом δ > 0. Улучшение достигнуто за счет привлечения интерполяции специального вида — так называемого быстрого преобразования Фурье  . До настоящего времени результат Шенхаге—Штрассена остается рекордным. Шенхаге на основе этого алгоритма умножения предложил алгоритм  нахождения íîä(a0 , a1 ), сложность которого допускает оценку O(m log2 m log log m), где m — битовая длинабольшего числа a0 (в примере . было показано, что алгоритм Евклида имеет сложность Θ(m2 )).Необходимо сказать, что преимущества по времени выполнениярассмотренных алгоритмов перед наивным умножением и алгоритмом Евклида проявляются лишь при очень больших значениях m.С умножением матриц положение таково, что обобщения алгоритма Штрассена в духе обобщения, предложенного Тоомом для алгоритма Карацубы, до сих пор не найдено.

Используя другие идеи, Д. Копперсмит и С. Виноград в  г. предложили алгоритм со сложностьюO(n2,376 ), где n — порядок перемножаемых квадратных матриц  . Этотрезультат остается рекордным по сей день. Существует ли для любого ǫ > 0 алгоритм умножения матриц со сложностью O(n2+ǫ ) — этооткрытый вопрос.Об алгоритме Шенхаге—Штрассена см., например, [, разд. .].См., например, [, разд. .].См. [].ЗадачиЗадачи. Игра «Ханойские башни».

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

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