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

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

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) в сумма-

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

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

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

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

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

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

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

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

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

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

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

2(i + l)log«.

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

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