КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Битовые операции
Каждый алгоритм строится на основе некоторого фиксированного набора базовых операций, и, согласно определениям из § 1, алгебраическая сложность алгоритма рассматривается при допущении, что затратность операций не зависит от размеров операндов. С позиций компьютерной арифметики это допущение вполне приемлемо, если каждый из операндов умещается в одном слове памяти. Но оно перестает быть приемлемым, если разрешаются операнды любой длины и вычисления проводятся в рамках арифметики многократной точности (арифметики длинных чисел). Здесь анализ сложности должен исходить из других принципов. Приемлемой является, например, следующая модель как система допущений, принимаемых нами при анализе алгоритмов. Число представляется набором бит, являющихся содержимым его двоичных разрядов (знак числа — тоже бит, например, обычно знаки + и -изображаются соответственно нулем и единицей), и все арифметические операции сводятся, в конечном счете, к битовым операциям. В качестве битовых операций могут выступать булевы операции V, Л, (другая нотация: or, and, not) при интерпретации 1 = «истина», О = «ложь» встречающихся бит; эти операции считаются равнозатрат-ными. Все биты, участвующие в записи числа, считаются равнодоступными. Можно смотреть на все это так, что ячейки памяти машины содержат по одному биту каждая, а в остальном действует принцип РАМ—ячеек бесконечно много и они в любой момент равнодоступны. Это— битовая модель вычислений (соответствующее сокращение БМ может расшифровываться как «битовая модель» и как «битовая машина»). Для анализа сложности с использованием БМ нет необходимости переписывать алгоритмы, детализируя их до уровня битовых опера- Глава 5. Битовая сложность ций. Вместо этого можно рассматривать привлекаемые алгоритмом базовые арифметические операции как основанные на битовых вычислениях процедуры, полагая временные и пространственные затраты алгоритма равными числу затрачиваемых битовых операций и, соответственно, требующихся дополнительных бит памяти. В качестве размера входа часто рассматривается либо суммарная битовая длина всего входа (всех входных данных), либо максимум этих длин. В некоторых случаях вместо битовых длин целых чисел берутся сами эти числа. Возможно и использование нескольких параметров размера входа. Определение 19.1. Пусть выбран какой-то размер входа. Рассмотрение каждой из базовых операций алгоритма А как процедуры, основанной на битовых вычислениях, и измерение затрат на выполнение А для каждого конкретного входа в битовых операциях или, соответственно, в хранимых дополнительных битах, приводит к битовой сложности (временной или пространственной) алгоритма А. Для нахождения битовой сложности какого-либо алгоритма, построенного на основных арифметических операциях над целыми числами, полезно знать битовые сложности самих основных арифметических операций. Мы исследуем школьные алгоритмы сложения, вычитания, умножения и деления «столбиком» неотрицательных целых чисел в двоичной системе. В процессе сложения «столбиком» мы шаг за шагом вычисляем двоичные цифры суммы, продвигаясь от младших разрядов к старшим. При этом в старшие разряды каждый раз переносится 0 или 1. Таким образом, на каждом шаге мы работаем с тремя битами (на начальном шаге, когда рассматриваются самые младшие разряды, бит переноса полагаем равным нулю). Для сложения многозначных чисел нам нужны две битовые процедуры трех аргументов (два аргумента— это цифры одноименных разрядов двух данных чисел, третий— это бит переноса из предшествующих разрядов), одна из процедур дает цифру соответствующего разряда суммы, вторая—новый бит переноса в старшие разряды. Мы не станем рассматривать этот вопрос более подробно, потому что и без деталей ясно, что затраты по построению каждого разряда суммы ограничены сверху некоторой константой. Алгоритм сложения «столбиком» будем обозначать буквами Add, от английского слова addition —сложение. Обозначим через а и Ъ операнды алгоритма (a, b eN+), через т1,т2 — их битовые длины: т 1 = А(а), т 2 = А(Ь). § 19. Битовые операции Лемма 19.1. Количество СТш{а,Ъ) битовых операций, затрачиваемых при сложении аиЪ «столбиком», удовлетворяет неравенствам тт{тъ т2} s= СТш(а, Ъ) s= c (max{ m lJ m2} + 1), (19.1) где с — некоторая положительная константа. Доказательство. Принимая во внимание замечание относитель В дальнейшем будем полагать m = max{ m 1, m 2}. (19.2) Предложение 19.1. Пусть Т*м(т) — сложность по числу битовых операций алгоритма сложения «столбиком» при использовании т в качестве размера входа. Тогда T*dd(m) = 6(m). Доказательство. При фиксированном т мы можем выбрать а и Ъ Алгоритм сложения «столбиком» позволяет получать сумму а и Ъ на месте максимального из этих двух чисел, в этом случае для битовой пространственной сложности имеем S ^d(m) = 0(l). Если для суммы чисел используется дополнительное место (чтобы не изменять данные слагаемые), то, соответственно, S ^d(m) = m + 0(1). Утверждения леммы 19.1 и предложения 19.1 верны, как легко убедиться, и для операции вычитания (при вычитании «столбиком» в старших разрядах занимается 0 или 1; битовая длина разности не превосходит т). Формула T*dd(m) = в(т) говорит о том, что алгоритм сложения «столбиком» при рассмотрении т в качестве размера входа является оптимальным по порядку битовой сложности: мы не можем игнорировать содержимое разрядов, и поэтому т является нижней границей битовой сложности алгоритмов сложения. Для алгоритмов умножения и деления «столбиком» в дальнейшем будет показано, что их Глава 5. Битовая сложность сложность имеет порядок т2, и в этой ситуации уже ниоткуда не следует, что не может существовать алгоритмов с лучшей асимптотикой сложности, и такие алгоритмы действительно существуют (мы об этом еще будем говорить). Поэтому умножение и деление «столбиком» мы будем называть, как это делается в некоторых книгах, наивным умножением и делением соответственно, используя обозначения NM и ND (от английских слов naive multiplication/division —наивное умножение/деление). Сложение «столбиком» будем просто называть сложением. Пример 19.1. Допустим, что для умножения двух целых положительных чисел а и Ъ мы используем сложения: а + а, (а + а)+а,..., {а +...+а)+а. (19.3) Ь-1 Исследуем битовую сложность такого «сверхнаивного» умножения, считая т размером входа. В силу леммы 19.1 при тг = т2 = т на каждое сложение уйдет не менее т битовых операций. Учитывая, что Ъ > 2т-г, получаем для исследуемой сложности оценку П{2тт). С другой стороны, аЪ < 22т, поэтому результат каждого шага в (19.3) имеет не превосходящую 2т битовую длину. Это означает, что число битовых операций на каждом из шагов не превосходит с • 2т, где с — константа. Отсюда получаем оценку 0(2 mm), и в итоге — оценку 6(2 mm). Наряду с размером входа (19.2) часто рассматривают два параметра тът2 размера входа. Предложение 19.2. Если рассмотреть два параметра тг = А (а), m 2 = A(b) размера входа, то битовая сложность Т**А(.тът2) алгоритма сложения будет допускать оценку в(шах{т1,т2}). Доказательство. Пусть, например, max{ m 1, m 2} = m 1. Тогда оцен Битовая сложность рассматривается не только в связи с арифметическими задачами. Например, булевы матрицы смежности, которые служат одним из стандартных средств представления графов без кратных ребер, являются битовыми матрицами, и целому ряду алгоритмов решения задач на графах естественным образом сопоставляется битовая сложность. Об этом будет идти разговор в § 23. Но прежде, § 20. Наивная арифметика: умножение в § 20 и 21, мы займемся битовой сложностью наивного умножения и деления. Еще одно замечание в заключение этого параграфа. Битовый анализ может учесть мельчайшие затраты, связанные с выполнением алгоритма. Вопрос в том, нужен ли настолько детализированный подход, коль скоро компьютеры выполняют операции над основными структурами данных на уровне слов, длина же слова—это, как правило, 64 бита. В связи с этим иногда вместо битовой рассматривается так называемая словесная сложность1. Но принципиальной разницы между битовой и словесной сложностью нет. Можно сказать так, что битовая сложность предполагает использование системы счисления с основанием 2, а словесная — с основанием 64. Анализ словесной сложности не является, в сравнении с анализом битовой сложности, ни более легким, ни более информативным.
Дата добавления: 2014-01-11; Просмотров: 824; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |