Структуры данных и модели вычислений
Равнодоступная адресная машина
Равнодоступная адресная машина (РАМ) — это числовая модель вычислительного устройства. Эта модель является наиболее близкой из рассмотренных к реальным вычислительным машинам и позволяет наиболее реалистично применять теоретические оценки сложности алгоритмов к реальным вычислениям.
Память машины состоит из регистров (ячеек). Каждый регистр имеет адрес и может содержать произвольное число. Регистр с номером 0 называется сумматором.
Программа — последовательность пронумерованных команд. Команда имеет вид
Коды операций
Операнд может быть одного из трех видов
где — натуральное число.
Содержимое регистра с номером обозначим через . Значение операнда определяется в зависимости от его вида следующим образом.
При оценке сложности алгоритмов используют в зависимости от обстоятельств разные веса команд. При работе с малыми числами и малым числом регистров реалистичным оказывается так называемый равномерный вес, при котором каждая команда требует единицу времени. При работе с большими числами и большим количеством регистров используется так называемый логарифмический вес команды, при котором время выполнения команды зависит как от значения операнда, так и от значения его адреса.
При определении веса команды используется функция , выражающая длину записи числа
Основание логарифма при получении асимптотических оценок не имеет существенного значения.
Вес операнда определяется в зависимости от его вида следующим образом:
| очередное число | ||
| очередное число | ||
| печать | ||
| переход на команду с номером | 1 | |
| переход на команду с номером , если | ||
| переход на команду с номером , если | ||
| конец вычислений | 1 |
Например, команда имеет логарифмический вес
Временная сложность программы определяется как сумма весов всех выполненных команд с учетом их многократного выполнения.
Емкостная сложность программы определяется как сумма по всем регистрам длин максимальных чисел, побывавших в этих регистрах.
Пример.
Рассмотрим вычисление :
Этот псевдокод легко может быть заменен РАМ-программой, представленной в таблице 12.2.
