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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 16: Строка 16:
Обычно рассматривается поведение указанных выше сложностных функций в пределе при увеличении размера входа, поскольку именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом.
Обычно рассматривается поведение указанных выше сложностных функций в пределе при увеличении размера входа, поскольку именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом.


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


==Литература==
==Литература==

Версия от 18:01, 25 мая 2009

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

При равномерном весовом критерии считается, что каждая команда затрачивает одну единицу времени и каждая ячейка занимает одну единицу памяти.

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

Временная сложность в худшем случае (или просто временная сложность) РАМ --- это функция [math]\displaystyle{ f_{max}(n) }[/math], равная наибольшей (по всем входам размера [math]\displaystyle{ n }[/math]) из сумм времен, затраченных на каждую сработавшую команду при обработке одного входа размера [math]\displaystyle{ n }[/math]. Временная сложность в среднем --- это среднее [math]\displaystyle{ f_{ave}(n) }[/math], взятое по всем входам размера [math]\displaystyle{ n }[/math], тех же самых сумм. Временная сложность в лучшем случае --- это функция [math]\displaystyle{ f_{min}(n) }[/math], равная наименьшей (по всем входам размера [math]\displaystyle{ n }[/math]) из сумм времен, затраченных на каждую сработавшую команду при обработке одного входа размера [math]\displaystyle{ n }[/math].

При равновероятном появлении входов значение [math]\displaystyle{ f_{ave}(n) }[/math] равно сумме времен, затраченных на каждую сработавшую команду при обработке всех входов размера [math]\displaystyle{ n }[/math], деленной на количество входов размера [math]\displaystyle{ n }[/math].

Такие же понятия определяются для емкости памяти, только вместо "времен, затраченных на каждую сработавшую команду", надо подставить в определение фразу: "емкость всех ячеек, к которым было обращение".

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

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

Литература

[Ахо-Хопкрофт-Ульман],

[Касьянов/88],

[Евстигнеев-Касьянов/94],

[Касьянов/95]