Что представляет собой одну операцию/цикл/перемещение в модели RAM?

Question

Я увидел диаграмму модели RAM, которая отображала входную ленту, выходную ленту, программу (только для чтения), указатель инструкции и регистры памяти. Однако, когда я смотрю на вопросы сложности времени, важно, сколько времени программа должна тратить на одно действие. Скажем, вы хотите прочитать один целочисленный символ из ленты для чтения, добавить его в целое число из регистра памяти, а затем вписать результат в ленточную ячейку, а затем переместите головку чтения вправо, а головка записи - один на слева. Сколько времени или сколько ходов я просто тратил?

Answer 1

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

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

Стандартная модель RAM состоит из конечного контроля, в которой хранится программа, один или несколько аккумулятор регистрируют $ acc $, счетчик инструкций и бесконечную коллекцию регистров памяти $ r [0], r [1], ldots $. Инструкция можно разделить на четыре категории:

• Контроль потока: безусловный прыжок, принять, отвергать, остановить, условные прыжки («Условия» просты, как $ acc = 0? $);

• Ввод/Вывод: Читать, написать;

• передача данных между аккумулятором и памятью: загрузка, сохранение;
• арифметика: $ acc: = 0 $, добавить $ r [i] $ to $ acc $;

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