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

Память компьютера, необходимая алгоритму

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

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

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

Аналогично классам временной сложности DTIME(f(n)) и NTIME(f(n)) , классы сложности DSPACE(f(n)) и NSPACE(f(n)) являются наборами языков, которые разрешимы детерминированными (соответственно, недетерминированными) машинами Тьюринга , использующими пространство. Классы сложности PSPACE и NPSPACE позволяют быть любым полиномом, аналогично P и NP . То есть, и ${\displaystyle O(f(n))}$ ${\displaystyle f}$ $${\displaystyle {\mathsf {PSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})}$$ $${\displaystyle {\mathsf {NPSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})}$$

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

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

Имеют место следующие ограничения между классами сложности. ^[2] $${\displaystyle {\mathsf {DTIME}}(f(n))\subseteq {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DTIME}}\left(2^{O(f(n))}\right)}$$

Более того, теорема Сэвича дает обратное утверждение, что если ${\displaystyle f\in \Omega (\log(n)),}$ $${\displaystyle {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DSPACE}}\left((f(n))^{2}\right).}$$

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

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

LOGSPACE

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

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

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

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

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

Смотрите также

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

Ссылки

1. Куо, Уэй; Цзо, Мин Дж. (2003), Оптимальное моделирование надежности: принципы и приложения, John Wiley & Sons, стр. 62, ISBN 9780471275459
2. Арора, Санджив ; Барак, Боаз (2007), Вычислительная сложность: современный подход (PDF) (черновик), стр. 76, ISBN 9780511804090
3. Иммерман, Нил (1988), «Недетерминированное пространство замкнуто относительно дополнения» (PDF) , SIAM Journal on Computing , 17 (5): 935–938, doi :10.1137/0217058, MR  0961049
4. Селепсени, Роберт (1987), «Метод форсирования недетерминированных автоматов», Бюллетень EATCS , 33 : 96–100
5. Нисан, Ноам (1992), «RL ⊆ SC», Труды 24-го симпозиума ACM по теории вычислений (STOC '92) , Виктория, Британская Колумбия, Канада, стр. 619–623, doi :10.1145/129712.129772, ISBN 0-89791-511-9, S2CID  11651375{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ).
6. Рейнгольд, Омер ; Тревизан, Лука ; Вадхан, Салил (2006), «Псевдослучайные блуждания по регулярным орграфам и проблема RL против L» (PDF) , STOC'06: Труды 38-го ежегодного симпозиума ACM по теории вычислений , Нью-Йорк: ACM, стр. 457–466, doi :10.1145/1132516.1132583, ISBN 1-59593-134-1, MR  2277171, S2CID  17360260