1.3. ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ РАМ-ПРОГРАММ

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

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

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

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

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

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

Логарифмический весовой критерий основан на грубом допущении, что цена выполнения команды (ее вес) пропорциональна длине ее операндов. Например, рассмотрим вес команды Сначала мы должны определить трудность декодирования операнда, представленного адресом. Просмотр целого числа занимает время Затем, чтобы прочитать содержимое с регистра и определить его местоположение, понадобится время Наконец, считывание содержимого требует время Так как команда прибавляет целое число к целому числу в

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

Рис. 1.11. Логарифмические веса команд РАМ, где вес операнда а, а обозначает метку.

сумматоре, то ясно, что разумным весом, который следует придать команде является

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

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

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

времени, и поэтому на выполнение всех команд MULT тратится время При логарифмическом весовом критерии команда MULT занимает время так что время выполнения всех команд MULT равно

что составляет

Емкостная сложность определяется числами, которые хранились в регистрах от до 3. При равномерном весовом критерии емкостная сложность составляет а при логарифмическом — поскольку наибольшее целое число среди содержавшихся в этих регистрах есть пп, а Таким образом, сложности для программы из примера 1.1 таковы:

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

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

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