С.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (1121252), страница 6
Текст из файла (страница 6)
Для асимптотической сложности в среднемтоже могут применяться подобные методы.Пусть на некотором вероятностном пространстве задана последовательность случайныхвеличин ξ1 , ξ 2 , ... и числовая последовательность h1 , h2 , ... такая, что выполнено неравенство:n⎧⎫E(ξ k ξ1 , ..., ξ k −1 ) ≤ hk . Зафиксируем q ≥ 0 и рассмотрим цело число τ = min ⎨n : ∑ ξ k ≥ q ⎬ .⎩ k =1⎭τ⎛⎞Тогда E⎜ ∑ nk ⎟ ≥ q .⎝ i=1 ⎠Этот факт позволяет доказывать, что число шагов алгоритма ≥ q .Для алгоритма поиска максимального и минимального элемента массива асимптотическаяоценка снизу сложности в среднем равна:⎧3⎪⎪ 2 n − 2, если n - чётноеf ( n) = ⎨⎪ 3 n − 2 + 1 , если n - нечётное2n⎩⎪ 229Битовая сложностьКогда мы занимались алгебраической сложностью, при её исследовании мы считалибитовую длину операндов не важной, за исключением случаев, когда в качестве размеравхода выбиралась битовая длина.
В случае, когда алгоритмы предназначены для исполненияна вычислительных машинах, битовая длина операндов становится существенной.При исследовании алгоритма на битовую сложность числа представляются строками(«словами») бит (но не «битов») и операции над числами рассматриваются как операции надотдельными битами, которые в свою очередь считаются равнозатратными. В битовой модели(машине) все биты считаются равнодоступными (в отличие от машины Тьюринга, гдеячейки ленты нельзя считать равнодоступными).Мы бы хотели исследовать битовую сложность алгоритмов и интересуемся количествомбитовых операций.
Работа эта более кропотливая и детальная, поэтому ограничимсяарифметическими операциями.На первый взгляд кажется, что если мы хотим исследовать битовую сложность какого-тоалгоритма, то нам нужно переписать его в битовых операциях. Но никто так не делает.Вместо этого полагают наличие соответствующих арифметических процедур (сложение,вычитание и т.д.).Рассмотрим целую арифметику. Будем считать, что числа заданы в двоичном виде.Итак, у арифметической операции 2 аргумента: a и b. Что в этом случае считать размеромвхода? Возможны следующие варианты: 1) размером входа можно считать сами числа a и b;2) битовую длину операндов: ma = ν (a ) ; mb = ν (b) ; 3) m = max{ma , mb } ; 4) ma + mb .Операция сложения (Add).Для затрат битового сложения справедлива оценка:Tmin{ma , mb } ≤ C Add(a, b) ≤ c(max{ma , mb }+ 1)где c — некоторая постоянная, не зависящая от a и b. Действительно, для сложениястолбиком на каждом этапе, исходя их 3-х бит на входе (слагаемые и возможный перенос),нужно получить 2 бита (результат и перенос), откуда следует оценка сверху.
Оценка снизутоже понятна, т.к. мы должны поработать с каждым битом меньшего числа.*Получим асимптотику для сложности в следующем виде: TAdd(m) = Θ(m) . Для этогодостаточно доказать соответствующие оценки снизу и сверху. Оценка сверху следует извышеприведённой оценки для затрат, а для оценки снизу можно взять два числа содинаковой длинной: ma = mb . Тогда min{ma , mb } = max{ma , mb } , и в силу оценки для затратполучаем требуемую оценку снизу для сложности.Для пространственной сложности получаем следующие оценки: в случае формирования*результата на месте большего числа — S Add(m) = O(1) ; в случае формирования результата на*новом месте — S Add(m) = m + O(1) .Алгоритмы умножения через сложение и деления через вычитание будем называть«наивными».Пример.«Сверхнаивное» умножение.
Для вычисления 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 операций, что доказывает оценку снизу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
