Сложность РАМ: различия между версиями

'''Сложность РАМ‎''' (''[[Complexity of RAM]]'') — Имеются два подхода к определению времени, необходимого для выполнения команд [[равнодоступная адресная машина|''равнодоступной адресной машины (РАМ)'']], и объема памяти, используемого каждым регистром ''РАМ''.

''[[Логарифмический весовой критерий]]'' учитывает  ограниченность размера реальной ячейки памяти в ЭВМ и основывается на предположении, что объем памяти, необходимый для хранения значения, равен длине двоичного представления этого значения (т.е. для целого числа <math>n>0</math>

Временная сложность ''в худшем случае'' (или просто ''[[временная сложность]]'') ''РАМ'' — это функция <math>f_{max}(n)</math>, равная наибольшей (по всем входам размера <math>n</math>) из сумм

времен, затраченных на каждую сработавшую команду при обработке одного входа размера <math>n</math>. Временная сложность в среднем — это среднее <math>f_{ave}(n)</math>, взятое по всем входам размера <math>n</math>, тех же самых сумм. Временная сложность ''в лучшем случае'' — это функция <math>f_{min}(n)</math>, равная наименьшей

''РАМ'' с [[логарифмический весовой критерий|''логарифмическим весовым критерием'']] и [[машина Тьюринга|''машины Тьюринга'']] полиномиально связаны. При ''равномерном весовом критерии'' нет полиномиальной связи между ''РАМ''  и ''МТ'', поскольку за линейное время на ''РАМ''  можно вычислить экспоненциальную функцию, но любую ''МТ'' с временной сложностью <math>T(n)</math> можно промоделировать некоторой ''РАМ'' за время <math>O(T(n))</math>.

* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —  М.: Мир, 1979.

* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.