Jump to content

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

(Перенаправлено со страницы «Сложность памяти »)

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

Подобно временной сложности , пространственная сложность часто выражается асимптотически в обозначении большого О , например: и т. д., где n — характеристика входных данных, влияющая на сложность пространства.

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

[ редактировать ]

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

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

[ редактировать ]

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

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

Более того, теорема Савича дает обратное утверждение: если

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

Теорема Иммермана – Селепшени утверждает, что опять же для замкнуто относительно дополнения. Это показывает еще одно качественное различие между классами временной и пространственной сложности, поскольку недетерминированные классы временной сложности не считаются закрытыми при дополнении; например, предполагается, что NP ≠ co-NP . [3] [4]

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

[ редактировать ]

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

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

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

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

[ редактировать ]

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

См. также

[ редактировать ]
  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, номер домена : 10.1145/1132516.1132583 , ISBN  1-59593-134-1 , МР   2277171 , S2CID   17360260
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 2cfdadd2de7c51c5e14f5e8a3939f17d__1719376380
URL1:https://arc.ask3.ru/arc/aa/2c/7d/2cfdadd2de7c51c5e14f5e8a3939f17d.html
Заголовок, (Title) документа по адресу, URL1:
Space complexity - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)