Оглавление
Сложность пространства
-
Определение пространственной сложности
- Пространственная сложность – объем памяти, необходимый для выполнения алгоритма.
- Включает пространство для входных данных и вспомогательную память.
-
Классы сложности пространства
- DSPACE и NSPACE – классы сложности, определяемые асимптотическими функциями.
- PSPACE и NPSPACE – классы, включающие многочлены.
-
Теорема о пространственной иерархии
- Для каждой конструктивной функции существует проблема, решаемая с определенным объемом памяти, но не с меньшим.
-
Ограничения между классами сложности
- DTIME(f(n)) ⊆ DSPACE(f(n)) ⊆ NSPACE(f(n)) ⊆ DTIME(2O(f(n))).
- Теорема Савича: NSPACE(f(n)) ⊆ DSPACE((f(n))2).
- PSPACE = NPSPACE, что указывает на незначительное различие между детерминированными и недетерминированными алгоритмами.
-
L или LOGSPACE
- Задачи, решаемые с использованием O(log n) памяти.
- Ограничены постоянным количеством переменных.
- Важны для обработки больших объемов данных.
-
Сложность вспомогательного пространства
- Вспомогательное пространство – это пространство, отличное от используемого для ввода.
- Определяется через машину Тьюринга с отдельной входной лентой.
- Сложность вспомогательного пространства анализируется через рабочую ленту.
Полный текст статьи: