02.01.055 Модель вычислений RAM - justjune/AiSD2026 GitHub Wiki

Предполагается, что алгоритм выполняется на воображаемом компьютере, который называется машиной с произвольным доступом к памяти или (RAM-модели). Этот компьютер работает следующим образом:

• для исполнения любой простой операции (+, -, *, =, if, call) требуется один элементарный шаг;
• циклы и подпрограммы являются не простыми, а состоят из последовательности простых операций. Число шагов исполнения цикла и подпрограммы зависит от количества повторений цикла или объема данных для подпрограммы;
• каждое обращение к памяти является простой операцией. Объем памяти считается неограниченным и однородным (физические различия реальных видов памяти: кэш, диск, оперативная не учитываются).

Быстродействие исполнения алгоритма в RAM-модели вычисляется, как сумма шагов, требующихся алгоритму для решения предложенного экземпляра задачи.

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