С.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (1121252), страница 10
Текст из файла (страница 10)
Далее подгоняем длины обоих чисел к2 ⎡log2 m ⎤ , приписывая незначащие нули. Тогда для сложности алгоритма получим:()()(TKM (m) = O 3⎡log2 m ⎤ = O 3log2 m = { log 2 m = log 2 3 ⋅ log 3 m } = O m log2 3)При этом log 2 3 = 1,58... < 2 . Если вспомнить алгоритм «наивного» умножения, то для негобыла получена оценка Θ(m 2 ) , поэтому алгоритм Карацубы в этом плане лучше.Чтобы иметь возможность сравнивать этот алгоритм с другими, нужно иметь для негооценку снизу. Её можно получить. Давайте подсчитаем общее число умноженийоднобитовых чисел.
Их количество будет⎧1, k = 0⎩3τ (k − 1), k > 0τ (k ) ≥ ⎨()⇒ τ (k ) ≥ 3k , что даёт нам возможность написать TKM (m) = Θ m log2 3 .Далее речь пойдёт об алгоритме Штрассена для умножения матриц (SM). Пусть A и B —квадратные матрицы. Если их порядки чётные ( n = 2l ), то мы можем их «разрезать»пополам:⎡AA = ⎢ 11⎣ A21A12 ⎤⎡B, B = ⎢ 11⎥A22 ⎦⎣ B21B12 ⎤B22 ⎥⎦Далее если мы попробуем их перемножить «в лоб», то нам потребуется 8 умножений матрицпорядка l.
Штрассен предлагает алгоритм, использующий в этом случае 7 умножений, ночисло сложений в этом случае будет не меленькое:45X 1 = ( A11 + A22 )(B11 + B22 )X 5 = ( A11 + A12 )B22X 3 = A11 (B12 − B22 )X 7 = ( A12 − A22 )(B21 + B22 )X 2 = ( A21 + A22 )B11X 6 = ( A21 − A11 )(B11 + B12 )X 4 = A22 (B21 − B11 )C11 = X 1 + X 4 − X 5 + X 7C12 = X 3 + X 5C21 = X 2 + X 4C22 = X 1 + X 3 − X 2 + X 6C12 ⎤⎡CAB = ⎢ 11⎥⎣C21 C22 ⎦()(TSM (n) = Θ 7 ⎡log2 n ⎤ = Θ 7 log2 n)Пользуясь тем же приёмом, что и в алгоритме Карацубы, получим()TSM (n) = Θ n log2 7 , log 2 7 = 2,807... < 3 .Вернёмся к алгоритму Карацубы: если разбиваем на 2 части, то нужно 3 умножения.Возникает идея: можно ли разбивать на p частей, чтобы требовалось q умножений чиселlog qменьшей длины ( Θ n p )? В алгоритме Карацубы p = 2 , q = 3 .
Можно ли подобрать p и qтак, чтобы log был ещё меньше? Ответ на этот вопрос дал А.Л.Тоом, который показал, чтодля любого p можно предложить алгоритм разбиения чисел длины p k на части p k −1 и()(использующий 2 p − 1 умножений: Θ nlog p ( 2 p −1)). Обратим внимание на следующее:⎛⎛⎛1 ⎞1 ⎞1 ⎞⎟⎟ = log p 2 p + log p ⎜⎜1 −⎟⎟ = 1 + log p 2 + log p ⎜⎜1 −⎟⎟log p (2 p − 1) = log p 2 p⎜⎜1 −⎝ 2p ⎠⎝ 2p ⎠⎝ 2p ⎠Последние 2 слагаемых приведённого равенства с ростом p стремятся к нулю, поэтомуlog p (2 p − 1) → 1 при p → ∞ , т.е. ∀ε > 0 ∃ алгоритм умножения со сложностью Ο(n1+ε ) .Отметим, что Штрассену удалось из других соображений предложить метод умножения,допускающий оценку O(n log n log log n ) , которая лучше полученной.Тоом в своём методе «резал» числа более чем на 2 части.
Казалось бы, что для матрицможно применить такой же подход и получить оценку вроде O(n 2+ε ) . Оказывается, чтоничего подобного. Но останавливаться на этом факте мы здесь не будем.Отметим, что в литературе по теории сложности указывается более короткий путь анализасоотношений, получаемых из алгоритмов, действующих по принципу «разделяй и властвуй».На этот счёт формулируется соответствующая теорема, часто называемая master theorem. Кпримеру, в пособии В.Б.Алексеева эта теорема формулируется следующим образом:Теорема (о рекуррентном неравенстве). Пусть f (n) — функция натурального аргумента,пусть C — натуральное число, C ≥ 2 , и a, b, α — вещественные константы, причём α > 0 ,и пусть для всех n вида Ck, k = 1, 2, ...
выполнено неравенство⎛n⎞f (n) ≤ af ⎜ ⎟ + bnα⎝C ⎠[]Пусть при этом f (n) монотонно не убывает на каждом отрезке вида C k + 1, C k +1 . Тогда приn → ∞ для всех n выполняется46( )( )()⎧O nα , α > log C a⎪f (n = ⎨O n logC a , α < log C a⎪ α⎩O n log n , α = log C aПосмотрим, даёт ли нам эта теорема что-то новое.
Пусть C = 2 , тогда n = 2 k иассоциированным уравнением для рекуррентного неравенства из условия теоремы будетt (k ) = a ⋅ t (k − 1) + b ⋅ (2k )αили, что то же самое,t (k ) = a ⋅ t (k − 1) + b ⋅ (2α ) .kКорнем соответствующего характеристического уравнения будет λ = a и дальнейшеерешение рекуррентного соотношения будет зависеть от того, совпадает ли 2α с a, чтоэквивалентно равенству α = log 2 a . Так, если α ≠ log 2 a , то, учитывая доминанты, получимпервые 2 строчки утверждаемого соотношения. Тем самым убеждаемся, чтосформулированное ранее предложение весьма схоже с этой теоремой.Всё это получается для чисел вида 2 k .
Если переходить к общему случаю, то, используямонотонность, нужно рассматривать на одном из концов отрезка. Но монотонность не всегдаочевидна, поэтому в этом вопросе следует проявлять осторожность (уже рассматривалсяпример сложности алгоритма возведения в степень RS, которая не обладает монотонностью).И ещё: теорема даёт оценку сверху, а для сравнения алгоритмов, только оценки сверху недостаточно.47СводимостьПусть имеются две задачи P и Q. Под «задачей» будем понимать следующую пару:1) вычислительное задание;2) соглашения о размере входа и о том, в чём измеряются вычислительныезатраты.Размер входа будем в дальнейшем всегда считать целым неотрицательным числом,сложность всегда будем считать однопараметрической функцией. Заметим сразу, чтосформулированные допущения нас вовсе не обременяют.Определение.
Будем говорить, что задача P не сложнее Q, если для любого алгоритма AQ ,решающего задачу Q найдётся алгоритмTAP (n) = O TAQ (n) .()AP , решающий задачу P, такой, чтоОбозначение: P ≤ Q .Отметим сразу, что это бинарное отношение транзитивно. И ещё одно важное дополнение:жизнь не столь проста, как кажется. Определением, сформулированным выше, на практикеприходится пользоваться редко.
В связи с этим принимаются дополнительные соглашения осложностях рассматриваемых алгоритмов, которые мы сформулируем ниже, а пока ихобозначим. Оговаривается, что сложности растут не слишком медленно и не слишкомбыстро. Эти соглашения иногда доказуемы, иногда выводятся из правдоподобности. Такжене рассматриваются «второсортные» алгоритмы, т.е. «на каждый хороший алгоритмрешения задачи Q найдётся хороший алгоритм, решающий задачу P».Определение.
Задачи P и Q, для которых одновременно верно P ≤ Q и Q ≤ P , будемназывать эквивалентными (по сложности).Обозначение: P >< Q .Далее рассмотрим пример.Пример. Раньше про деление мы почти ничего не говорили, кроме того, что его можнореализовать на базе умножения. Рассмотрим следующие задачи:M:умножение 2-х целых чисел a и bD:деление целого a битовой длины ≤ 2m на целое b битовой длины mS:возведение в квадрат целого aR:обращение целого aВ задаче R имеется в виду не точное вычисление, а до m двоичных разрядов послезапятой.
Для задачи D — построение m двоичных цифр частного, не зависимо отположения запятой.Покажем, что M >< D >< S >< R .Для начала сформулируем ограничения, которые будем предполагать выполненными:1) сложность любого из рассматриваемых алгоритмов f (m) является неубывающейфункцией;2) для сложности верно f (m) ≥ m (растёт не слишком медленно);3) для f (αm) верно: αf (m) ≤ f (αm) ≤ α 2 f (m) , для любого вещественного α > 1 .48Полное доказательство мы здесь приводить не будем (его можно найти в книге«Построение и анализ вычислительных алгоритмов» из рекомендуемой литературы) ирассмотрим его лишь в общих чертах.Начнём с того, что докажем M ≤ S .
Для этого нужно показать, что для любогоалгоритма AS , решающего задачу S, найдётся алгоритм AM , решающий задачу M,такой, что будет выполнена оценка: TAM (m) = O TAS (m) .()()1(a + b )2 − a 2 − b 2 . Это соотношение2даёт нам алгоритм вычисления произведения, используя операцию возведения встепень. Очевидно, что сложение и вычитание имеет линейную по времени сложность,а деление на 2 вообще выполняется за даром (деление на 2 эквивалентно сдвигу всехразрядов числа на 1 бит вправо). Поэтому для сложности такого алгоритма получаем:Воспользуемся следующим соотношением: ab =TAM (m) = TAS (m + 1) + 2TAS (m) + O(m)12314243" + " и "− "( a +b ) 21)3)TAS (m + 1) ≤ TAS (2m) ≤ 4TAS (m) (в силу сформулированных ограничений 1 и 3)()⇒ TAM (m) = O TAS (m) .Теперь докажем, что S ≤ R .
Будем считать, что у нас есть алгоритм AR , решающийзадачу R — обращения целого числа. Воспользуемся равенством:a2 =111−a a +1−aЗаметим, что в итоге мы должны получить целое число ( a 2 ), в то время как в правойчасти равенства стоят совсем не целые величины. Дотошные авторы в умных книжкахговорят, что в обращении надо брать 3m цифр после запятой. Умножаем на 23m ,получая целое число, и обращаем. Затем, глядя на последние 4 цифры, можно получитьцелый ответ, сделав некоторую поправку. TAS (m) = O TAR (3m) и с учётом пункта 3()()ограничений, получаем TAS (m) = O TAR (m) .Покажем, что R ≤ M .
В этом случае одной формулой обойтись не получится ипридётся привлечь математический анализ. Построим последовательность x0 , x1 , x2 , ... ,1сходящуюся к . Такую последовательность, например, можно описать рекуррентнойaформулой: xi = 2 xi−1 − axi2−1 . Соотношений такого рода можно привести не одно, ноособенностью такой формулы является то, что она родственна с методом касательныхрешения уравнения на отрезке (если сходится, то очень быстро: сходимостьквадратичная, а не линейная). Кроме того, исследуя несколько первых цифр числа a,11можно выбрать x0 так, что≤ x0 ≤ и для элементов последовательности будет2aa11выполнено: xi = (1 − ε ) , xi+1 = (1 − ε 2 ) .
С учётом нулевого приближения, дляaa11элементов последовательности будет верно, что xi − ≤ 2i . У приближенийa 2отбрасываем концы (те цифры, которые не заслуживают доверия). Используя тот факт,49что сумма геометрической прогрессии имеет порядок последнего члена, получаем, чтоTAR (m) = O TAM (m) .()Тем самым доказано, что M ≤ S ≤ R ≤ M ⇒ M >< S >< R .Следующим этапом покажем, что D ≤ M , используя, что M >< R . Будем исходить изa1того, что = a ⋅ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
