Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 36
Текст из файла (страница 36)
Добавление нулейвхода есть число вида 2k . При использовании стратегии «разделяйи властвуй» это облегчает и описание алгоритма, и анализ его сложности. С теоретической точки зрения для задачи умножения двух целых чисел a и b мы можем предполагать, что битовая длина каждогоиз данных чисел равна 2k , гдеk = max{⌈log2 λ(a)⌉, ⌈log2 λ(b)⌉},(.)так как всегда возможно добавить спереди любого из данных чиселнекоторое количество нулей.
Если речь идет об умножении квадратных матриц A и B произвольного порядка n, то мы можем добавитьк матрицам несколько нулевых строк и столбцов так, чтобы сделатьих порядки равными 2⌈log2 n⌉ :A 0B 0AB 0(.)0 00 00 0(нулями обозначены нулевые блоки соответствующего размера).Несмотря на переход от начальных данных к более громоздким, некоторые из алгоритмов, основанных на стратегии «разделяй и властвуй» и использующих этот переход, имеют существенно меньшуюсложность, чем наивные алгоритмы.Предложение .. Пусть вещественная функция f натуральногоаргумента такова, что f (n) = f (2⌈log2 n⌉ ) для всех n ∈ N+ и¨u,если k = 0,kf (2 ) ¶wf (2k−1 ) + ϕ (2k ), если k > 0,при k ∈ N, где u, w — вещественные числа, причем u ¾ 0, w ¾ 1, а ϕ —неотрицательная функция, определенная для всех n ∈ N+ .
Тогда привсех n ∈ N+ выполняется неравенство(u, l mесли n = 1,(.)f (n) ¶n⌈log2 n⌉+ ϕ (2), если n > 1.wf2Доказательство. Легко видеть, чтоl mmln= ⌈log2 n⌉ − 1.log22(.)l mnВ самом деле, если 2k−1 < n ¶ 2k , k > 1, то 2k−2 <¶ 2k−1 , т. е. ес2ll mmnли ⌈log2 n⌉ = k, то log2= k − 1. Для случая n = 2⌈log2 n⌉ неравен2ство (.) выполнено по условию,для остальных случаев используемl mn= f (2⌈log2 ⌈n/2⌉⌉ ) = f (2⌈log2 n⌉−1 ).равенства f (n) = f (2⌈log2 n⌉ ), f2Глава . Рекуррентные соотношения и сложность алгоритмовТеорема .. Пусть вещественная функция f натурального аргумента такова, что f (n) = f (2⌈log2 n⌉ ) для всех n ∈ N+ и¨u,если k = 0,kf (2 ) ¶wf (2k−1 ) + c(2k )d , если k > 0,при k ∈ N, где u, d ¾ 0, c > 0, w ¾ 1.
Тогда при рассмотрении f какфункции, определенной для всех n ∈ N+ , выполняются оценкиdO(n log n), если d = log2 w,df (n) = O(n ),если d > log2 w,log2 wO(n),если d < log2 w.Доказательство следует из предложения . и теоремы ..Подобно тому, как доказательство теоремы . было преобразовано в доказательство теоремы ., из приведенного выше доказательства мы можем получить доказательство следующей теоремыТеорема ..
Пусть вещественная функция f натурального аргумента такова, что f (n) = f (2⌈log2 n⌉ ) для всех n ∈ N+ и¨u,если k = 0,kf (2 ) ¾wf (2k−1 ) + c(2k )d , если k > 0,где u, d ¾ 0, c > 0, w ¾ 1. Тогда для функции f (n), при рассмотренииее как функции, определенной для всех n ∈ N+ , выполненоdΩ(n log n), если d = log2 w,log2 wf (n) = Ω(n),если d > log2 w,dΩ(n ),если d < log2 w.Перейдем к примерам.Пример . (умножение Карацубы). Пусть a и b — целые положительные числа битовой длины m = 2k .
Положив l = 2k−1 , можемзаписатьa = e2l + f , b = g2l + h,где e, f , g, h — целые числа битовой длины l. А. А. Карацубе принадлежит замечательное наблюдение, позволяющее вычислить произведение ab, выполнив всего три умножения чисел половинной длины,несколько сдвигов (домножений на 2m и 2l ) и несколько аддитивныхопераций над числами битовой длины ¶ 2m:ab = eg22l + ((e + f )(g + h) − eg − fh)2l + fh,(.)§ . Добавление нулейтогда как обычное раскрытие скобок в (e2l + f )(g2l + h) требует выполнения четырех таких умножения:ab = eg22l + (eh + fg)2l + fh.(.)Мы видим, что формула (.) использует произведения eg, fh,(e + f )(g + h), а формула (.) — произведения eg, eh, fg, fh.Небольшая проблема, которая выше была замаскирована словами «половинная длина», состоит в том, что битовая длина любогоиз чисел e + f , g + h, входящей в произведение (e + f )(g + h), можетоказаться равной l + 1, а не l.
Но еслиe + f = e1 2l + f1 ,g + h = g1 2l + h1 ,где e1 , g1 — однобитовые числа (0 или 1), то(e + f )(g + h) = e1 g1 22l + (e1 h1 + g1 f1 )2l + f1 h1 .(.)Произведение f1 h1 вычисляется рекурсивным обращением к алгоритму, произведения e1 g1 , e1 h1 , g1 f1 , как и все сложения и сдвиги, требуют O(l) операций.Равенство (.) и предположение, что m = 2k , приводят к рекурсивному алгоритму Карацубы умножения целых положительных чисел (будем обозначать этот алгоритм буквами KM: первая из этихбукв — начальная в фамилии автора алгоритма, вторая — в английском слове multiplication — умножение). Предположение m = 2k приводит к следующему соотношению для битовой сложности умножения Карацубы:(1, если m = 1,(.)TKM (m) ¶m+ cm, если m > 1,3TKM2где c — некоторая положительная константа.Умножение Карацубы при произвольном входе a, b ∈ N+ размера m = max{λ(a), λ(b)} предполагает, что сначала мы находим k == ⌈log2 m⌉, затем добавляем спереди каждого из a, b некоторое количество нулей так, чтобы битовая длина каждого из сомножителейстала равной 2k , а после этого используем рекурсивный алгоритм,основанный на (.).Мы можем применить теорему . (w = 3, d = 1), так как припроизвольном m ∈ N+ выполняется TKM (m) = TKM (2⌈log2 m⌉ ).
Получаем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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
