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

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

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

Мы не станем рассматривать этотвопрос более подробно, потому что и без деталей ясно, что затратыпо построению каждого разряда суммы ограничены сверху некоторойконстантой.Алгоритм сложения «столбиком» будем обозначать буквами Add,от английского слова addition — сложение. Обозначим через a и bоперанды алгоритма (a, b ∈ N+ ), через m1 , m2 — их битовые длины:m1 = λ(a), m2 = λ(b).§ . Битовые операцииTЛемма ..

Количество CAdd(a, b) битовых операций, затрачиваемых при сложении a и b «столбиком», удовлетворяет неравенствамT(a, b) ¶ c(max{m1 , m2 } + 1),min{m1 , m2 } ¶ CAdd(.)где c — некоторая положительная константа.Доказательство. Принимая во внимание замечание относительно ограниченности затрат на построение каждого разряда суммы,а также то, что битовая длина суммы a + b не может превышатьTmax{m1 , m2 } + 1, получаем оценку CAdd(a, b) ¶ c(max{m1 , m2 } + 1).′Пусть m = min{m1 , m2 }. Очевидно, что m′ младших цифр суммы a + bполучаются выполнением битовых операций над соответствующимицифрами обоих слагаемых и битами переноса (в то время как частьцифр старших разрядов большего из слагаемых может быть простоперенесена в старшие разряды суммы). Это дает нам неравенствоTmin{m1 , m2 } ¶ CAdd(a, b).В дальнейшем будем полагатьm = max{m1 , m2 }.(.)∗Предложение ..

Пусть TAdd(m) — сложность по числу битовых операций алгоритма сложения «столбиком» при использовании m∗в качестве размера входа. Тогда TAdd(m) = Θ(m).Доказательство. При фиксированном m мы можем выбрать a и bтак, что m1 = m2 = m, тогда min{m1 , m2 } = max{m1 , m2 } = m; далееприменяем лемму ..Алгоритм сложения «столбиком» позволяет получать сумму a и bна месте максимального из этих двух чисел, в этом случае для битовой пространственной сложности имеем S∗Add (m) = O(1). Если длясуммы чисел используется дополнительное место (чтобы не изменятьданные слагаемые), то, соответственно, S∗Add (m) = m + O(1).Утверждения леммы . и предложения . верны, как легкоубедиться, и для операции вычитания (при вычитании «столбиком»в старших разрядах занимается 0 или 1; битовая длина разности непревосходит m).∗Формула TAdd(m) = Θ(m) говорит о том, что алгоритм сложения«столбиком» при рассмотрении m в качестве размера входа являетсяоптимальным по порядку битовой сложности: мы не можем игнорировать содержимое разрядов, и поэтому m является нижней границей битовой сложности алгоритмов сложения.

Для алгоритмов умножения и деления «столбиком» в дальнейшем будет показано, что ихГлава . Битовая сложностьсложность имеет порядок m2 , и в этой ситуации уже ниоткуда неследует, что не может существовать алгоритмов с лучшей асимптотикой сложности, и такие алгоритмы действительно существуют (мыоб этом еще будем говорить). Поэтому умножение и деление «столбиком» мы будем называть, как это делается в некоторых книгах, наивным умножением и делением соответственно, используя обозначенияNM и ND (от английских слов naive multiplication/division — наивноеумножение/деление). Сложение «столбиком» будем просто называтьсложением.Пример ..

Допустим, что для умножения двух целых положительных чисел a и b мы используем сложения:a + a, (a + a) + a, ..., (a| + {z... + }a) + a.(.)b −1Исследуем битовую сложность такого «сверхнаивного» умножения,считая m размером входа. В силу леммы . при m1 = m2 = m накаждое сложение уйдет не менее m битовых операций. Учитывая,что b > 2m−1 , получаем для исследуемой сложности оценку Ω(2m m).С другой стороны, ab < 22m , поэтому результат каждого шага в (.)имеет не превосходящую 2m битовую длину.

Это означает, что число битовых операций на каждом из шагов не превосходит c · 2m, гдеc — константа. Отсюда получаем оценку O(2m m), и в итоге — оценкуΘ(2m m).Наряду с размером входа (.) часто рассматривают два параметра m1 , m2 размера входа.Предложение .. Если рассмотреть два параметра m1 = λ(a),∗∗m2 = λ(b) размера входа, то битовая сложность TAdd(m1 , m2 ) алгоритма сложения будет допускать оценку Θ(max{m1 , m2 }).Доказательство. Пусть, например, max{m1 , m2 } = m1 . Тогда оцен∗∗ка TAdd(m1 , m2 ) = Ω(max{m1 , m2 }) подтверждается наличием входа a =m1∗∗= 2 − 1, b = 2m2 − 1.

Оценка же TAdd(m1 , m2 ) = O(max{m1 , m2 }) следует из леммы ..Битовая сложность рассматривается не только в связи с арифметическими задачами. Например, булевы матрицы смежности, которыеслужат одним из стандартных средств представления графов без кратных ребер, являются битовыми матрицами, и целому ряду алгоритмов решения задач на графах естественным образом сопоставляетсябитовая сложность. Об этом будет идти разговор в § . Но прежде,§ .

Наивная арифметика: умножениев §  и , мы займемся битовой сложностью наивного умноженияи деления.Еще одно замечание в заключение этого параграфа. Битовый анализ может учесть мельчайшие затраты, связанные с выполнением алгоритма. Вопрос в том, нужен ли настолько детализированный подход, коль скоро компьютеры выполняют операции над основнымиструктурами данных на уровне слов, длина же слова — это, как правило,  бита. В связи с этим иногда вместо битовой рассматриваетсятак называемая словесная сложность  .

Но принципиальной разницымежду битовой и словесной сложностью нет. Можно сказать так, чтобитовая сложность предполагает использование системы счисленияс основанием 2, а словесная — с основанием 64. Анализ словеснойсложности не является, в сравнении с анализом битовой сложности,ни более легким, ни более информативным.§ . Наивная арифметика: умножение∗Предложение .. Пусть TNM(m) — временная битовая сложность наивного умножения при использовании m в качестве размера∗∗входа, а TNM(m1 , m2 ) — временная битовая сложность этого же алгоритма при использовании m1 , m2 в качестве двух параметров размеравхода. Тогда∗TNM(m) = Θ(m2 ),∗∗TNM(m1 , m2 ) = Θ(m1 m2 ).(.)Доказательство.

Затраты наивного умножения a на b связаны ссуммированием m2 чисел n1 , n2 , ..., nm2 , где каждое ni равно 0 илиa · 2i−1 в зависимости от соответствующей цифры в двоичной записи b. Несложной индукцией доказывается, что для si = n1 + n2 + ...... + ni , i = 1, 2, ..., m2 , выполнено λ(si ) ¶ m1 + i. Если ni+1 6= 0, то последние i цифр числа ni+1 суть нули, и при вычислении si+1 = si + ni+1мы не притрагиваемся к этим цифрам, а преобразуем si в si+1 сложением двух чисел, первое из которых образовано всеми разрядамичисла si , кроме i последних (согласно сказанному, битовая длина этого числа не превосходит m1 ), второе же слагаемое есть a, и его битовая длина равна m1 .

Число битовых операций, требующихся дляпреобразования si в si+1 , не превосходит c(m1 + 1) для некоторой положительной константы c. В том случае, когда все цифры числа bравны 1, это число при любом i не меньше, чем m1 , по лемме ..См., например, книгу []. В литературе на английском языке, в частности в книге [], используется термин «word complexity».Глава . Битовая сложностьПоэтому битовые затраты, связанные с наивным умножением a на b,не превосходят c(m1 + 1)m2 , а при b = 2m2 − 1 (двоичная запись этого b состоит только из единиц) затраты не меньше, чем m1 m2 .

Это∗∗дает оценку TNM(m1 , m2 ) = Θ(m1 m2 ).Рассмотрим теперь m как размер входа. Так как m1 ¶ m и m2 ¶ m,∗то затраты не превосходят c(m + 1)m, это дает оценку TNM(m) = O(m2).mС другой стороны, если m1 = m2 = m и a = b = 2 − 1, то затраты не∗могут быть меньше, чем m2 , и, следовательно, TNM(m) = Ω(m2 ). Таким∗2образом, TNM (m) = Θ(m ).Для пространственной битовой сложности наивного умножениямы имеем, очевидно, оценкиS∗NM (m) = 2m + O(1),S∗∗NM (m1 , m2 ) = m1 + m2 + O(1).Обсудим переход от параметров m1 , m2 размера входа к параметрам a, b (можно считать, что и к параметрам log a, log b — между a, bи log a, log b в этом смысле нет принципиальной разницы, так какодни параметры однозначно определяют другие; в то же время мыне можем восстановить a, b по ⌈log2 (a + 1)⌉, ⌈log2 (b + 1)⌉).Для перехода в верхних оценках сложности от λ(k) к log2 k, k ∈∈ N∗ , часто оказывается удобным простое неравенство ⌈log2 (k + 1)⌉ ¶¶ 2 log2 k, справедливое для всех k ¾ 2:⌈log2 (k + 1)⌉ = ⌊log2 k ⌋ + 1 ¶ log2 k + 1 ¶ 2 log2 k.Поэтому, например,m1 ¶ 2 log2 a,m2 ¶ 2 log2 bиm1 m2 ¶ 4 log2 a log2 b(.)для всех a, b ¾ 2.

Имеем для достаточно больших m1 , m2 и некоторойположительной константы cT∗∗CNM(a, b) ¶ TNM(m1 , m2 ) ¶ cm1 m2 ¶ 4c log2 a log2 b.TМы можем написать CNM(a, b) = O(log a log b), считая, что выражениепод знаком O рассматривается как функция двух переменных a, b,при этом a, b → ∞; считаем также, что логарифмы имеют общее основание (подобные предположения будут подразумеваться и в дальнейшем). Остается заметить, что битовая временная сложность прииспользовании самих a, b в качестве параметров размера входа совпадает с битовыми временными затратами.

Это позволяет получить∗∗из оценки TNM(m1 , m2 ) = O(m1 m2 ) оценку TNM (a, b) = O(log a log b) для§ . Наивная арифметика: умножениевременной битовой сложности при использовании двух параметровразмера входа a, b. Итак:При использовании самих положительных целых a, b в качествепараметров размера входа сложность наивного умножения a на b почислу битовых операций допускает оценку O(log a log b).Выше наивное умножение (умножение «столбиком») понималосьтак, что если какая-то цифра числа b равна нулю, то, несмотря наэто, построение соответствующих ni и si требует не менее m1 битовых операций. При таком взгляде сложность будет величинойΘ(log a log b).

Но можно считать, что в рассматриваемом случае битовые затраты на получение si не зависят от a и ограничены константой. Тогда оценка Ω(log a log b) места не имеет: если a = 2k1 , b = 2k2 ,где k1 , k2 — положительные целые, то битовые затраты будут ограничены линейной функцией от k1 , k2 .Пример .. Покажем, что битовая временная сложность алгоритма вычисления n! с помощью пошаговых наивных умножений2 · 3, (2 · 3) · 4, ..., (2 · 3...(n − 1)) · nпри использовании n в качестве размера входа допускает верхнююоценку O((n log n)2 ). В силу предложения . и неравенства (.)рассматриваемая сложность не превосходит cf (n), где c — некотораяположительная константа, а значение f (n) равноlog2 2 log2 3 + log2 (2 · 3) log2 4 + ...

+ log2 (2 · 3...(n − 1)) log2 n.Имеемf (n) ¶ log2 (2 · 3...(n − 1))(log2 2 + log2 3 + ... + log2 n) ¶ log22 (n!).Одним из следствий формулы Стирлинга является оценка log2 (n!) == O(n log n), откуда log22 (n!) = O((n log n)2 ), и f (n) = O((n log n)2 ).Пример .. Мы упоминали о том, что для алгоритма, входомкоторого является несколько целых чисел, можно в некоторых случаях определять размер входа как суммарную битовую длину всех этихчисел.

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

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