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

Чтобы точно определить временную и емкостную сложности, надо указать время, необходимое для выполнения каждой РАМ-команды, и объем памяти, используемый каждым регистром. Мы рассмотрим два таких весовых критерия для наших программ. При равномерном весовом критерии каждая РАМ-команда затрачивает одну единицу времени и каждый регистр использует одну единицу памяти. Если не оговорено противное, то сложность РАМ-программы будет измеряться в соответствии с равномерным весовым критерием.

Второе определение, иногда более реалистичное, принимает во внимание ограниченность размера реальной ячейки памяти и называется логарифмическим весовым критерием. Пусть /(/) - логарифмическая функция на целых числах, заданная равенствами

LlogliJ+l, i¥0, t = 0.

Таблица на рис. 1.10 дает логарифмические веса t{a) для всех трех возможных видов операнда а. На рис. 1.11 приведены веса РАМ-команд.

Здесь учитывается, что для представления целого числа п в регистре требуется logn J + 1 битов. Регистры же, напомним, могут содержать произвольно большие целые числа.

Логарифмический весовой критерий основан на грубом допу-ш,ении, что цена выполнения команды (ее вес) пропорциональна длине ее операндов. Например, рассмотрим вес команды ADD*i. Сначала мы должны определить трудность декодирования операнда, представленного адресом. Просмотр целого числа i занимает время Затем, чтобы прочитать содержимое с(i) регистра i и определить его местоположение, понадобится время l{c(i)). Наконец, считывание содержимого c{i) требует время l(c{c{i))). Так как команда ADD и прибавляет целое число c(c(j)) к целому числу с (0) в сумма-

Операнд а

Вес t(a)

l(i)+l{c{i))

l(i) + l(c(i)) + imi)))

ис. 1.10. Логарифмические веса операндов.



Команда

LOAD а

STORE i

i(cm+m

STORE *f

/(c(0)) + /(t) + /(c(i))

ADD a

/(c(0)) + (a)

SUB a

/(c(0)) + /(a)

MULT a

/(c(0)) + /(a)

DIV a

/(c(0)) + (a)

READ i

/(ВХОД) + /(1)

READ *t

/(вход + /(1) + Дс(0)

WRITE a

JUMP Й

JGTZ b

JZERO Й

HALT

Рис. 1.11. Логарифмические веса команд РАМ, где (а) - вес операнда а, а b

обозначает метку.

торе, то ясно, что разумным весом, который следует придать команде ADD *i, является I (с (0))+/ (0+/ (с (0)+/ (с(с (i))).

Определим логарифмическую емкостную сложность РАМ-программы как сумму по всем работавшим регистрам, включая сумматор, величин / {Xi), где Xj- наибольшее по абсолютной величине целое число, содержавшееся в t-м регистре за все время вычислений.

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

Оценим временную и емкостную сложности РАМ-программы из примера 1.1, вычисляющей п". При подсчете временной сложности будет доминировать цикл с командой MULT. Когда эта команда выполняется i-й раз, сумматор содержит п, а регистр 2 содержит п. Всего команда MULT выполняется п-1 раз. При равномерном весовом критерии каждая команда MULT требует одну единицу вре-



Равномерный вес

Логарифмический вес

Временная сложность

0(п)

0 {rfl log п)

Емкостная сложность

0(1)

0 (п log п)

Для этой программы равномерный вес реалистичен только в ситуации, когда столь большое целое, как п", записывается в виде одного машинного слова. Если п" превышает то, что можно представить одним машинным словом, то даже логарифмическая временная сложность до некоторой степени нереалистична, поскольку она предполагает, что два целых числа i и / перемножаются за время 0(/(t)+/(/)), а возможность этого неизвестна.

Для программы из примера 1.2 в предположении, что п - длина входного слова, временные и емкостные сложности таковы:

Равномерный вес

Логарифмический вес

Временная сложность

0(п)

0(л2 log п)

Емкостная сложность

0(1)

0 (п log п)

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

мени, и поэтому на выполнение всех команд MULT тратится время 0{п). При логарифмическом весовом критерии i-я команда MULT занимает время 1{п)+1{п)!и{1+1) log п, так что время выполнения всех команд MULT равно

2(i + l)log«.

что составляет О (л" log п).

Емкостная сложность определяется числами, которые хранились в регистрах от О до 3. При равномерном весовом критерии емкостная сложность составляет 0(1), а при логарифмическом - 0{п log п), поскольку наибольшее целое число среди содержавшихся в этих регистрах есть п", а / {п")рип log п. Таким образом, сложности для программы из примера 1.1 таковы:





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.0038