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