Пространственная сложность

Пространственная сложность алгоритма в или структуры данных — это объем памяти, необходимый для решения экземпляра вычислительной задачи, зависимости от характеристик входных данных. Это память, необходимая алгоритму до его полного выполнения. Сюда входит пространство памяти, используемое его входами, называемое входным пространством , и любая другая (вспомогательная) память, которую он использует во время выполнения, которая называется вспомогательным пространством .

Подобно временной сложности , пространственная сложность часто выражается асимптотически в обозначении большого О , например: $O(n),$$O(n\log n),$ $O(n^{\alpha }),$ $O(2^{n}),$ и т. д., где n — характеристика входных данных, влияющая на сложность пространства.

Классы пространственной сложности

Аналогично классам временной сложности DTIME(f(n)) и NTIME(f(n)) классы сложности DSPACE(f(n)) и NSPACE(f(n)) представляют собой наборы языков, которые разрешимы детерминированными методами ( соответственно, недетерминированные) Машины Тьюринга , использующие $O(f(n))$ космос. Классы сложности PSPACE и NPSPACE позволяют $f$ быть любым полиномом, аналогично P и NP . То есть,

$${\mathsf {PSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})$$

и

$${\mathsf {NPSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})$$

Отношения между классами

Теорема о пространственной иерархии утверждает, что для всех пространственно-конструируемых функций $f(n),$ существует проблема, которую можно решить с помощью машины с $f(n)$ памяти, но не может быть решена машиной с асимптотически меньшими $f(n)$ космос.

Имеют место следующие ограничения между классами сложности.

$${\mathsf {DTIME}}(f(n))\subseteq {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DTIME}}\left(2^{O(f(n))}\right)$$

Более того, теорема Савича дает обратное утверждение: если $f\in \Omega (\log(n)),$

$${\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DSPACE}}\left((f(n))^{2}\right).$$

Как прямое следствие, ${\mathsf {PSPACE}}={\mathsf {NPSPACE}}.$ Этот результат удивителен, поскольку предполагает, что недетерминизм может лишь незначительно уменьшить пространство, необходимое для решения проблемы. Напротив, гипотеза экспоненциального времени предполагает, что для временной сложности может существовать экспоненциальный разрыв между детерминированной и недетерминированной сложностью.

Теорема Иммермана – Селепшени утверждает, что опять же для $f\in \Omega (\log(n)),$ ${\mathsf {NSPACE}}(f(n))$ замкнуто относительно дополнения. Это показывает еще одно качественное различие между классами временной и пространственной сложности, поскольку недетерминированные классы временной сложности не считаются закрытыми при дополнении; например, предполагается, что NP ≠ co-NP .

ПРОСТРАНСТВО ЖУРНАЛА

Основная статья: L (сложность)

L или LOGSPACE — это набор задач, которые может решить детерминированная машина Тьюринга, используя только $O(\log n)$ пространство памяти относительно размера ввода. Даже один счетчик, который может индексировать всю $n$-битовый ввод требует $\log n$ пространство, поэтому алгоритмы LOGSPACE могут поддерживать только постоянное количество счетчиков или других переменных одинаковой битовой сложности.

LOGSPACE и другие сублинейные пространственные сложности полезны при обработке больших данных, которые не могут поместиться в оперативную память компьютера . Они связаны с алгоритмами потоковой передачи , но ограничивают только объем используемой памяти, в то время как алгоритмы потоковой передачи имеют дополнительные ограничения на то, как входные данные подаются в алгоритм.Этот класс также находит применение в области псевдослучайности и дерандомизации , где исследователи рассматривают открытую проблему того, является ли L = RL .

Соответствующий класс сложности недетерминированного пространства — NL .

Сложность вспомогательного пространства

Термин Вспомогательное пространство относится к пространству, отличному от того, которое используется для ввода.Сложность вспомогательного пространства можно формально определить в терминах машины Тьюринга с отдельной входной лентой , на которую нельзя записывать, а только читать, и обычной рабочей лентой, на которую можно записывать.Затем сложность вспомогательного пространства определяется (и анализируется) с помощью рабочей ленты.Например, рассмотрим поиск в глубину сбалансированного двоичного дерева с $n$ узлы: сложность его вспомогательного пространства равна $\Theta (\log n).$

См. также

• Анализ алгоритмов - Исследование ресурсов, используемых алгоритмом.
• Теория сложности вычислений . Неотъемлемая сложность вычислительных задач.
• Вычислительный ресурс — что-то, что необходимо компьютеру для решения проблемы, например этапы обработки или память.