2.2. Машина с произвольным доступом к памяти

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

С учетом того, что алгоритмы реализуются в виде компьютерных программ, в большинстве случаев в качестве технологии анализа алгоритмов будет использоваться модель обобщенной однопроцессорной машины с произвольным доступом к памяти (Random-Access Machine - RAM). В этой модели команды процессора выполняются последовательно; операции, выполняемые одновременно, отсутствуют.

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

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

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