Глава 5

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

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

Каждый алгоритм строится на основе некоторого фиксированного набора базовых операций, и, согласно определениям из § 1, алгебра­ическая сложность алгоритма рассматривается при допущении, что затратность операций не зависит от размеров операндов. С позиций компьютерной арифметики это допущение вполне приемлемо, если каждый из операндов умещается в одном слове памяти. Но оно пере­стает быть приемлемым, если разрешаются операнды любой длины и вычисления проводятся в рамках арифметики многократной точ­ности (арифметики длинных чисел). Здесь анализ сложности должен исходить из других принципов.

Приемлемой является, например, следующая модель как систе­ма допущений, принимаемых нами при анализе алгоритмов. Число представляется набором бит, являющихся содержимым его двоичных разрядов (знак числа — тоже бит, например, обычно знаки + и -изображаются соответственно нулем и единицей), и все арифмети­ческие операции сводятся, в конечном счете, к битовым операци­ям. В качестве битовых операций могут выступать булевы операции V, Л, ­ (другая нотация: or, and, not) при интерпретации 1 = «истина», О = «ложь» встречающихся бит; эти операции считаются равнозатрат-ными. Все биты, участвующие в записи числа, считаются равнодо­ступными.

Можно смотреть на все это так, что ячейки памяти машины со­держат по одному биту каждая, а в остальном действует принцип РАМ—ячеек бесконечно много и они в любой момент равнодоступ­ны. Это—битовая модель вычислений (соответствующее сокращение БМ может расшифровываться как «битовая модель» и как «битовая машина»).

Для анализа сложности с использованием БМ нет необходимости переписывать алгоритмы, детализируя их до уровня битовых опера-

134

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

ций. Вместо этого можно рассматривать привлекаемые алгоритмом базовые арифметические операции как основанные на битовых вы­числениях процедуры, полагая временные и пространственные затра­ты алгоритма равными числу затрачиваемых битовых операций и, соответственно, требующихся дополнительных бит памяти. В каче­стве размера входа часто рассматривается либо суммарная битовая длина всего входа (всех входных данных), либо максимум этих длин. В некоторых случаях вместо битовых длин целых чисел берутся сами эти числа. Возможно и использование нескольких параметров разме­ра входа.

Определение 19.1. Пусть выбран какой-то размер входа. Рассмот­рение каждой из базовых операций алгоритма А как процедуры, ос­нованной на битовых вычислениях, и измерение затрат на выпол­нение А для каждого конкретного входа в битовых операциях или, соответственно, в хранимых дополнительных битах, приводит к би­товой сложности (временной или пространственной) алгоритма А.

Для нахождения битовой сложности какого-либо алгоритма, по­строенного на основных арифметических операциях над целыми чис­лами, полезно знать битовые сложности самих основных арифмети­ческих операций. Мы исследуем школьные алгоритмы сложения, вы­читания, умножения и деления «столбиком» неотрицательных целых чисел в двоичной системе.

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

Алгоритм сложения «столбиком» будем обозначать буквами Add, от английского слова addition —сложение. Обозначим через а и Ъ операнды алгоритма (a, beN⁺), через т₁,т₂ — их битовые длины: т₁ = А(а), т₂ = А(Ь).