Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 28

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

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

Здесь анализ сложности долженисходить из других принципов.Приемлемой является, например, следующая модель как система допущений, принимаемых нами при анализе алгоритмов. Числопредставляется набором бит, являющихся содержимым его двоичныхразрядов (знак числа — тоже бит, например, обычно знаки + и −изображаются соответственно нулем и единицей), и все арифметические операции сводятся, в конечном счете, к битовым операциям. В качестве битовых операций могут выступать булевы операции∨, ∧, ¬ (другая нотация: or, and, not) при интерпретации 1 = «истина»,0 = «ложь» встречающихся бит; эти операции считаются равнозатратными. Все биты, участвующие в записи числа, считаются равнодоступными.Можно смотреть на все это так, что ячейки памяти машины содержат по одному биту каждая, а в остальном действует принципРАМ — ячеек бесконечно много и они в любой момент равнодоступны.

Это — битовая модель вычислений (соответствующее сокращениеБМ может расшифровываться как «битовая модель» и как «битоваямашина»).Для анализа сложности с использованием БМ нет необходимостипереписывать алгоритмы, детализируя их до уровня битовых опера-Глава . Битовая сложностьций. Вместо этого можно рассматривать привлекаемые алгоритмомбазовые арифметические операции как основанные на битовых вычислениях процедуры, полагая временные и пространственные затраты алгоритма равными числу затрачиваемых битовых операций и,соответственно, требующихся дополнительных бит памяти. В качестве размера входа часто рассматривается либо суммарная битоваядлина всего входа (всех входных данных), либо максимум этих длин.В некоторых случаях вместо битовых длин целых чисел берутся самиэти числа.

Возможно и использование нескольких параметров размера входа.Определение .. Пусть выбран какой-то размер входа. Рассмотрение каждой из базовых операций алгоритма A как процедуры, основанной на битовых вычислениях, и измерение затрат на выполнение A для каждого конкретного входа в битовых операциях или,соответственно, в хранимых дополнительных битах, приводит к битовой сложности (временной или пространственной) алгоритма A.Для нахождения битовой сложности какого-либо алгоритма, построенного на основных арифметических операциях над целыми числами, полезно знать битовые сложности самих основных арифметических операций. Мы исследуем школьные алгоритмы сложения, вычитания, умножения и деления «столбиком» неотрицательных целыхчисел в двоичной системе.В процессе сложения «столбиком» мы шаг за шагом вычисляемдвоичные цифры суммы, продвигаясь от младших разрядов к старшим.

При этом в старшие разряды каждый раз переносится 0 или 1.Таким образом, на каждом шаге мы работаем с тремя битами (на начальном шаге, когда рассматриваются самые младшие разряды, битпереноса полагаем равным нулю). Для сложения многозначных чисел нам нужны две битовые процедуры трех аргументов (два аргумента — это цифры одноименных разрядов двух данных чисел, третий — это бит переноса из предшествующих разрядов), одна из процедур дает цифру соответствующего разряда суммы, вторая — новыйбит переноса в старшие разряды.

Мы не станем рассматривать этотвопрос более подробно, потому что и без деталей ясно, что затратыпо построению каждого разряда суммы ограничены сверху некоторойконстантой.Алгоритм сложения «столбиком» будем обозначать буквами 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.

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

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