Сложность РАМ: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Сложность РАМ''' ([[Complexity of RAM | '''Сложность РАМ''' (''[[Complexity of RAM]]'') — Имеются два подхода к определению времени, необходимого для выполнения команд [[равнодоступная адресная машина|''равнодоступной адресной машины (РАМ)'']], и объема памяти, используемого каждым регистром ''РАМ''. | ||
При [[равномерный весовой критерий|''равномерном весовом критерии'']] считается, что каждая команда затрачивает одну единицу времени и каждая ячейка занимает одну единицу памяти. | При [[равномерный весовой критерий|''равномерном весовом критерии'']] считается, что каждая команда затрачивает одну единицу времени и каждая ячейка занимает одну единицу памяти. | ||
[[Логарифмический весовой критерий | ''[[Логарифмический весовой критерий]]'' учитывает ограниченность размера реальной ячейки памяти в ЭВМ и основывается на предположении, что объем памяти, необходимый для хранения значения, равен длине двоичного представления этого значения (т.е. для целого числа <math>n>0</math> | ||
требуется <math>\log n</math> единиц памяти), а время исполнения команды пропорционально длине ее операндов. | требуется <math>\log n</math> единиц памяти), а время исполнения команды пропорционально длине ее операндов. | ||
Временная сложность ''в худшем случае'' (или просто [[временная сложность | Временная сложность ''в худшем случае'' (или просто ''[[временная сложность]]'') ''РАМ'' — это функция <math>f_{max}(n)</math>, равная наибольшей (по всем входам размера <math>n</math>) из сумм | ||
времен, затраченных на каждую сработавшую команду при обработке одного входа размера <math>n</math>. Временная сложность в среднем | времен, затраченных на каждую сработавшую команду при обработке одного входа размера <math>n</math>. Временная сложность в среднем — это среднее <math>f_{ave}(n)</math>, взятое по всем входам размера <math>n</math>, тех же самых сумм. Временная сложность ''в лучшем случае'' — это функция <math>f_{min}(n)</math>, равная наименьшей | ||
(по всем входам размера <math>n</math>) из сумм времен, затраченных на каждую сработавшую команду при обработке одного входа размера <math>n</math>. | (по всем входам размера <math>n</math>) из сумм времен, затраченных на каждую сработавшую команду при обработке одного входа размера <math>n</math>. | ||
| Строка 16: | Строка 16: | ||
Обычно рассматривается поведение указанных выше сложностных функций в пределе при увеличении размера входа, поскольку именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. | Обычно рассматривается поведение указанных выше сложностных функций в пределе при увеличении размера входа, поскольку именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. | ||
''РАМ'' с [[логарифмический весовой критерий|''логарифмическим весовым критерием'']] и [[машина Тьюринга|''машины Тьюринга'']] полиномиально связаны. При | ''РАМ'' с [[логарифмический весовой критерий|''логарифмическим весовым критерием'']] и [[машина Тьюринга|''машины Тьюринга'']] полиномиально связаны. При ''равномерном весовом критерии'' нет полиномиальной связи между ''РАМ'' и ''МТ'', поскольку за линейное время на ''РАМ'' можно вычислить экспоненциальную функцию, но любую ''МТ'' с временной сложностью <math>T(n)</math> можно промоделировать некоторой ''РАМ'' за время <math>O(T(n))</math>. | ||
==Литература== | ==Литература== | ||
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. | |||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
[[Категория: Теория автоматов]] | [[Категория: Теория автоматов]] | ||
Версия от 13:22, 9 сентября 2011
Сложность РАМ (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].
Литература
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
- Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.