Главная Промышленная автоматика.

ностью 2п. Заметим, что измерение временной сложности есть не что иное, как подсчет числа арифметических операций. Емкостная сложность последовательности программ равна числу переменных, участвовавших в программе, снова как функции от п. Программы примера 1.4 имеют емкостную сложность п+4.

Определение. В случае когда в качестве модели вычислений берутся неветвящиеся программы, говорят, что данная задача имеет временную или емкостную сложность Од(/(п)), если найдется последовательность программ для ее решения с временной или емкостной сложностью не более с/(п) для некоторой постоянной с. (Од (/(«)) читается так: "порядка /(п) шагов неветвящейся программы". Индекс А снизу обозначает "арифметический" - это основная характеристика неветпящихся программ.) Таким образом, вычисление полинома имеет временную, а также и емкостную сложность Оа{п).

2. Битовые вычисления

Очевидно, что модель неветвящихся программ основана на равномерной весовой функции. Как мы уже отмечали, этот вес годится в предположении, что все вычисляемые величины имеют "разумный" размер. Существует простая модификация модели неветвящихся программ, которая соответствует логарифмической весовой функции. Эта модель, называемая битовым вычислением, по существу, является той же неветвящейся программой, но только в ней

1) все переменные принимают значения О или 1, т. е. это биты,

2) используются логические операции вместо арифметических ) (and обозначается через л, or -через V, exclusive or -через ф. not - через -i).

Для битовой модели арифметические операции над целыми числами i и / занимают по меньшей мере l{i)+l{j) шагов, что соответствует логарифмическому весу операндов. В самом деле, умножение и деление с помощью наилучших известных алгоритмов для умножения или деления i на / требуют более чем шагов.

При битовых вычислениях порядок величин обозначается через Об. Битовая модель полезна, когда речь идет об основных операциях, таких, как арифметические, которые исходны в других моделях. Например, для модели неветвящихся программ умножение двух п-разрядных двоичных целых чисел можно осуществить за Оа(1) шагов, тогда как для битовой модели наилучший известный результат - это Об {п log п log log п) шагов.

Другое применение битовой модели - логические сети (схемы). Неветвящиеся программы с двоичными входами и операциями вза-

) Таким образом, набор команд для наших РАМ должен состоять из этих операций.

3* 3S



имно однозначно соответствуют комбинационным логическим сетям, вычисляющим набор булевых функций. Число шагов такой программы - это число логических элементов в сети.

Пример 1.5. На рис. 1.17,а приведена программа для сложения двух двуразрядных чисел [uiaj и [Ь, bj. Выходные переменные - это такие числа Сц, Ci и Со, что [ui ag]+[biba]=[CiCicJ. Неветвящаяся программа на рис. 1.17, а вычисляет

с, = {{а,АК)®а,)®Ь„

с, = ((Go Л Ь„) Л (а, Vi)) V («1 Abx).

На рис. 1.17,6 изображена соответствующая логическая сеть. В качестве упражнения предлагаем показать, что сложение двух и-разрядных чисел можно выполнить за Об(п) шагов. □


и А i>Q

Of w 6 з:- и А иг у а, А 6,

Рис. 1.17, а - битовая программа для сложения; б - эквивалентная логическая

сеть.



3. Операции с двоичными векторами

Можно было бы не ограничивать значения переменных символами О и 1, а разрешить переменным принимать в качестве значения любой вектор из О и 1. Фактически двоичные векторы фиксированной длины очевидным образом соответствуют целым числам, так что здесь не допускается ничего такого, что не допускалось бы в РАЛ\, т. е., когда это удобно, просто разрешаются регистры неограниченного размера.

Однако, как мы увидим, в тех немногих алгоритмах, где применяется модель с двоичными векторами, длина векторов будет значительно больше числа битов, требуемых для представления размера задачи. Величина большинства целых чисел, фигурирующих в таком алгоритме, будет того же порядка, что и размер задачи. Например, решая задачу выбора пути в графе со 100 узлами можно было бы для представления наличия или отсутствия пути из данного узла V в каждый из узлов использовать двоичные векторы длины 100, а именно (-ю позицию в векторе для узла v занимает 1 тогда и только тогда, когда существует путь из у в Uj. В этой же задаче можно также использовать целые числа для счета и индексации, например, и они, вероятно, были бы размера числа 100. Таким образом, для целых чисел требовалось бы 7 битов, тогда как для векторов - 100 битов.

Хотя это сравнение и бросает некоторую тень на вычисления о двоичными векторами, большинство вычислительных машин выполняют логические операции на двоичных векторах, составляющих полное машинное слово, за одну команду. Поэтому двоичные векторы длины 100 можно было бы обрабатывать за три или четыре шага (вместо одного для чисел). Тем не менее на результаты о временной и емкостной сложностей алгоритмов при применении модели с двоичными векторами, мы должны смотреть сит grano salts ), ибо размер задачи, при котором модель становится нереалистичной, в этом случае много меньше, чем в случае моделей РАМ и неветвящихся программ. Порядок величин при применении модели с двоичными векторами мы будем обозначать через Одв-

4. Деревья решений

Мы рассмотрели три модификации РАМ, игнорирующие команды разветвления и учитывающие только те шаги программы, которые включают арифметический счет, В некоторых задачах удобно в качестве основной меры сложности брать число выполняемых команд разветвления В случае сортировки, например, выходы совпадают

) Буквально (с лат.) - с крупинкой соли; в первнисном смысле - с иронией, язьигельно.- Прим. ред.





0 1 2 3 4 5 6 7 [8] 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0037