С.А. Абрамов - Вычислительная сложность алгоритмов, страница 7

Для вычисления a ⋅ b вычисляются следующие суммы:a + a , (a + a) + a , … , (a + ... + a) + a . В качестве размера входа возьмём величину14243b −130m = max{ma , mb }. Рассмотрим случай, когда ma = mb = m , тогда b > 2 m−1 и общее числобитовых операций допускает оценку Ω(2 m m ) . ab < 2 2 m и, следовательно, результаткаждого сложения имеет не превосходящую 2m битовую длину, а значит числобитовых операций на каждом шаге ≤ c ⋅ 2m . Поскольку число шагов < 2 m , мы можем*( m) = Θ 2 m m .написать оценку O(2m m) .

В итоге поучаем оценку TNM()Посмотрим на сложность сложения в случае, когда в качестве размера входа выбираются 2параметра ma и mb :**TAdd(ma , mb ) = Θ(max{ma , mb }) .Заметим, что это не просто переписывание оценки через m. Покажем, откуда следует**TAdd(ma , mb ) = Ω(max{ma , mb }) . Доказательство оценки Ω заключается в описание«неудобных» данных для алгоритма:ma64748a = 11...101112...31mbb = 10...30112mbДля так выбранных входных данных становиться очевидным то, что для их сложенияпридётся поработать со всеми битами более длинного числа, что доказывает оценку с Ω .Для алгоритма «сверхнаивного» умножения из примера допустимы следующие оценкисложности: Ω 2 mb ma и O 2 mb (ma + mb ) , но в то же время, оценка Θ 2 max{ma ,mb } max{ma , mb }будет неверна.()()()Для алгоритма «наивного» умножения (NM) (обычное умножение столбиком) справедливы***(m) = Θ m 2 , TNM(ma , mb ) = Θ(ma mb ) .

Они легко следуютследующие оценки сложности: TNM( )из определения: требуется суммировать mb чисел n1 , ... , nmb , где ni либо 0, либо a ⋅ 2i −1 .Обозначим si = n1 + ... + ni , i = 1, ... , mb . Несложно индукцией показывается, что ν (si ) ≤ ma + i .Прибавляем ni +1 ≠ 0 . Последние i цифр этого числа равны нулю — мы их игнорируем:si +1 = si + ni +1 .Число битовых операций для преобразования si в si +1 не превосходит c(ma + 1) . Если всецифры числа b равны 1, то число битовых операций для вычисления произведения не**(ma , mb ) = Θ(ma mb ) .меньше, чем ma mb . Откуда получаем оценку для сложности: TNMЕсли будем рассматривать m = max{ma , mb } как размер входа, то затраты не превзойдут( )c(m + 1)m , откуда следует оценка для сложности O m 2 .

Оценку снизу выведем из**(ma , mb ) , рассмотрев случай ma = mb = m ⇒ затраты будут не меньше, чем ma mb = m 2 .TNM( )*( m) = Θ m 2 .Откуда получаем TNMДляпространственнойсложностибудутверныоценки:*(m) = 2m + O(1)S NM,**S NM(ma , mb ) = ma + mb + O(1) .Иногда удобно иметь оценки сложности, выраженные в самих a и b. Возникает вопрос:можно ли в вышеприведённых рассуждениях заменить ma mb на log a log b ? Для перехода воценках сверху от ν (c) к log 2 c удобно такое неравенство: ⎡log 2 (c + 1) ⎤ < 2 log 2 c , c ≥ 2 . Темсамым неравенства ma ≤ 2 log 2 a , mb ≤ 2 log 2 b дают нам возможность написать следующуюоценку:31TT**C NM(a, b) ≤ TNM(ma , mb ) ≤ cma mb ≤ 4c log 2 a log 2 b ⇒ C NM(a, b) = O(log a log b )Функция затрат в этом случае будет соответствовать сложности (т.к.

размер входа — a и b).**Тем самым доказано, что TNM(a, b) = O(log a log b) . Можно ли то же самое проделать дляустановления оценки Θ ? Ответ: нет, т.к. уже для a = 2k1 , b = 2k 2 оценка будет линейной.Рассмотрим задачу вычисления n! следующим образом: 2 ⋅ 3 ; (2 ⋅ 3) ⋅ 4 ; … ; (2 ⋅ ... ⋅ (n − 1) ) ⋅ n .()Докажем, что затраты допускают оценку O (n log n ) .2Очевидно, что затраты не превосходят c ⋅ f (n) , где f (n) = log 2 2 log 2 3 + log 2 (2 ⋅ 3)log 2 4 + ...

++ log 2 (2 ⋅ 3 ⋅ ... ⋅ (n − 1))log 2 n < log 2 (2 ⋅ 3 ⋅ ... ⋅ (n − 1))[log 2 3 + log 2 4 + ... + log 2 n] < log 2 n!log 2 n! .()Откуда следует оценка для сложности O log 2 n! , что эквивалентно, согласно формуле()Стирлинга, O (n log n ) .2Пример. Пусть имеются числа a1 , ...

, an > 0 , которые перемножаются наивным способом:a1a2 , (a1a2 )a3 , … , (a1 ⋅ ... ⋅ an −1 )an . Обозначим суммарную битовую длину черезnM = ∑ν (ai ) . Докажем, что битовая сложность такого алгоритма допускает оценкуi =12( ).OMПроведём доказательство, предполагая, что ai ≠ 1 (если есть единицы, то оценка темболее верна). Очевидно, что затраты алгоритма не превзойдут c ⋅ F (a1 , ... , an ) , гдеF (a1 , ... , an ) = log 2 a1 log 2 a2 + log 2 (a1a2 )log 2 a3 + ... + log 2 (a1 ⋅ ...

⋅ an −1 )log 2 an ≤≤ log 2 (a1a2 ...an −1 )[log 2 a2 + ... + log 2 an ] ≤ (log 2 a1 + log 2 a2 + ... + log 2 an ) ≤ {log 2 ai ≤ ν (ai )} ≤2≤ (ν (a1 ) + ν (a2 ) + ... + ν (an ) ) = M 2 .2Деление с остатком.Пусть даны два числа a ≥ b > 1 . Покажем, что для алгоритма «наивного» деления (ND)(деление столбиком) имеют место следующие оценки:( )***TND(m) = Θ m 2 , TND(ma , mb ) = Θ((ma − mb + 1)mb ) .На каждое вычитание уходит c(mb + 1) , количество вычитаний не превосходит (ma − mb + 1) ,**(ma , mb ) = O((ma − mb + 1)mb ) (единицей пренебречь нельзя, т.к. вполнеоткуда получаем TNDвозможно, что ma = mb , и выражение под знаком O превратится в нуль).Что касается нижней оценки, то можно рассмотреть числа a = 2ma − 1 и b = 2mb −1 , длякоторых алгоритму потребуется (ma − mb + 1)mb операций, что доказывает оценку снизу. Этодаёт возможность написать оценку через Θ .( )*Что касается оценки TND(m) = O m 2 , то она следует из того, что m 2 ≥ ma mb ≥ (ma − mb + 1)mb .Для доказательства нижней оценки, рассмотрим a = 2m − 1 и b = 2⎣ 2 ⎦ , которые являютсясамыми неудобными для алгоритма.

Это позволяет написать нижнюю оценку, что завершает*доказательство оценки TND( m) = Θ m 2 .m( )Когда a и b рассматриваются в качестве размера входа, то битовая сложность допускаетоценку O((log a − log b + a )log b ) ⇒ O (log a log b ) . Если брать только a, то O(log 2 a ) .32Пример. Пусть на входе имеется n и k ≥ 2 . Требуется перевести n из двоичной системысчисления к системе с основанием k. Покажем, что битовая сложность такогоалгоритма допускает оценку O(log 2 n ) .n в k-ичной записи формируется из остатков от деления чисел q0 , ...

, qt , t = ⎣log k n ⎦ + 1⎢q ⎥на k, где q0 = n , qi = ⎢ i −1 ⎥ , i = 1, ... , t . Все qi ≤ n , и общие затраты на всех шагах⎣ k ⎦допускают оценку O(log n log k log k n) , log 2 k log k n = log 2 n ⇒ O (log 2 n ) .14243 123затраты на числоодном шаге шагов ( t )Интересно, что если известен некоторый алгоритм умножения со сложностью TM (m) , то понему можно построить алгоритм деления со сложностью не хуже, чем O(TM (m) ) .Исследуем алгоритм Евклида на битовую сложность.

На входе два числа: a0 ≥ a1 > 0 . Ранеебыло сказано, что величина a0 не сильно влияет на алгебраическую сложность, т.к. послепервого же деления с остатком получим число, меньшее a1 . Но в случае битовой сложностиэто не так. Если в качестве размера входа взять a1 , то сложность будет бесконечной. Чтобыполучить информативную оценку битов можно в качестве размера входа взять a0 илиm = ν (a0 ) . Возьмём m , тогда можно показать, что для битовой сложности алгоритма( )Евклида имеет место оценка O m 2 .

Доказательство этого факта не очень сложное: очевидно,что затраты алгоритма не превзойдут величиныnc ⋅ ∑ (ν (ai −1 ) − ν (ai ) + 1)ν (ai ) .i =1Здесь под знаком суммы написана битовая сложность деления ai −1 на ai , причём числошагов алгоритма Евклида равно n. Функция ν (ai ) с ростом i убывает, поэтому мы можемнаписать следующую оценку:nnc ⋅ ∑ (ν (ai −1 ) − ν (ai ) + 1)ν (ai ) ≤ cnν (a0 ) + cν (a0 )∑ (ν (ai −1 ) − ν (ai )){ i =1i =1≥ν ( a1 )дальше эта сумма вычисляется легко:cnν (a0 ) + cν (a0 )(ν (a0 ) − ν (an )) ≤ cν (a0 )(n + ν (a0 )) .Всё хорошо, но в оценку влезло n.

Но n — это число шагов алгоритма Евклида и, как былополучено ранее, является величиной логарифмической: n ≤ 2 log 2 a1 + 1 ⇒ n ≤ 2 log 2 a0 + 1 ,( )откуда следует заявленная оценка O m 2 .()Т.к. эта оценка является верхней, то можно перейти к оценке через a0 : O log 2 a0 . Эта оценкаполучена на базе алгоритма «наивного» деления и возникает вопрос: если использоватьболее эффективный алгоритм деления, можно ли уменьшить оценку? Оказывается, что этоне так, и оценка точная.