§ 19. Битовые операции

135

Лемма 19.1. Количество С^Т_ш{а,Ъ) битовых операций, затрачива­емых при сложении аиЪ «столбиком», удовлетворяет неравенствам

тт{т_ъ т₂} s= С^Т_ш(а, Ъ) s= c(max{m_lJ m₂} + 1), (19.1)

где с — некоторая положительная константа.

Доказательство. Принимая во внимание замечание относитель­ но ограниченности затрат на построение каждого разряда суммы, а также то, что битовая длина суммы а + Ъ не может превышать тах{т_ът₂} + 1, получаем оценку C\_dd{a, Ъ) s= c(max{m₁, т₂} + 1). Пусть т! = min{m₁, т₂}. Очевидно, что т! младших цифр суммы а + Ъ получаются выполнением битовых операций над соответствующими цифрами обоих слагаемых и битами переноса (в то время как часть цифр старших разрядов большего из слагаемых может быть просто перенесена в старшие разряды суммы). Это дает нам неравенство тт{т_ът₂}^с1_АА(.а,Ъ). □

В дальнейшем будем полагать

m = max{m₁,m₂}. (19.2)

Предложение 19.1. Пусть Т*_м(т) — сложность по числу бито­вых операций алгоритма сложения «столбиком» при использовании т в качестве размера входа. Тогда T*_dd(m) = 6(m).

Доказательство. При фиксированном т мы можем выбрать а и Ъ так, что т_г = т₂ = т, тогда тт{т_ът₂} = max{m₁,m₂} = m; далее применяем лемму 19.1. □

Алгоритм сложения «столбиком» позволяет получать сумму а и Ъ на месте максимального из этих двух чисел, в этом случае для би­товой пространственной сложности имеем S^_d(m) = 0(l). Если для суммы чисел используется дополнительное место (чтобы не изменять данные слагаемые), то, соответственно, S^_d(m) = m + 0(1).

Утверждения леммы 19.1 и предложения 19.1 верны, как легко убедиться, и для операции вычитания (при вычитании «столбиком» в старших разрядах занимается 0 или 1; битовая длина разности не превосходит т).

Формула T*_dd(m) = в(т) говорит о том, что алгоритм сложения «столбиком» при рассмотрении т в качестве размера входа является оптимальным по порядку битовой сложности: мы не можем игнори­ровать содержимое разрядов, и поэтому т является нижней грани­цей битовой сложности алгоритмов сложения. Для алгоритмов умно­жения и деления «столбиком» в дальнейшем будет показано, что их

136

Глава 5. Битовая сложность

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

Пример 19.1. Допустим, что для умножения двух целых положи­тельных чисел а и Ъ мы используем сложения:

а + а, (а + а)+а, ..., {а + ...+а)+а. (19.3)

Ь-1

Исследуем битовую сложность такого «сверхнаивного» умножения, считая т размером входа. В силу леммы 19.1 при т_г = т₂ = т на каждое сложение уйдет не менее т битовых операций. Учитывая, что Ъ > 2^т-^г, получаем для исследуемой сложности оценку П{2^тт). С другой стороны, аЪ < 2^2т, поэтому результат каждого шага в (19.3) имеет не превосходящую 2т битовую длину. Это означает, что чис­ло битовых операций на каждом из шагов не превосходит с • 2т, где с — константа. Отсюда получаем оценку 0(2^mm), и в итоге — оценку 6(2^mm).

Наряду с размером входа (19.2) часто рассматривают два парамет­ра т_ът₂ размера входа.

Предложение 19.2. Если рассмотреть два параметра т_г = А (а), m₂ = A(b) размера входа, то битовая сложность Т**_А(.т_ът₂) алго­ритма сложения будет допускать оценку в(шах{т₁,т₂}).

Доказательство. Пусть, например, max{m₁,m₂} = m₁. Тогда оцен­ ка Т^_А(т_ъ т₂) = Г2(шах{т₁, т₂}) подтверждается наличием входа а = = 2^mi - 1, Ъ = 2^т? - 1. Оценка же Т**_А(.т_ъ т₂) = 0(max{m₁, m₂}) сле­ дует из леммы 19.1. □

Битовая сложность рассматривается не только в связи с арифмети­ческими задачами. Например, булевы матрицы смежности, которые служат одним из стандартных средств представления графов без крат­ных ребер, являются битовыми матрицами, и целому ряду алгорит­мов решения задач на графах естественным образом сопоставляется битовая сложность. Об этом будет идти разговор в § 23. Но прежде,