В этой главе мы обсудим сложность вычислительных задач с точки зрения количества места, которое требует алгоритм.
Пространственная сложность имеет много общих черт временной сложности и служит еще одним способом классификации задач в соответствии с их вычислительными сложностями.
Что такое космическая сложность?
Пространственная сложность — это функция, описывающая объем памяти (пространства), который занимает алгоритм с точки зрения количества входных данных для алгоритма.
Мы часто говорим о дополнительной памяти , не считая памяти, необходимой для хранения самого ввода. Опять же, мы используем натуральные (но фиксированной длины) единицы измерения для этого.
Мы можем использовать байты, но проще использовать, скажем, число используемых целых чисел, количество структур фиксированного размера и т. Д.
В конце концов, функция, которую мы придумаем, не будет зависеть от фактического количества байтов, необходимых для представления единицы.
Сложность пространства иногда игнорируется, потому что используемое пространство минимально и / или очевидно, однако иногда это становится такой же важной проблемой, как сложность времени
Определение
Пусть M будет детерминированной машиной Тьюринга (TM), которая останавливается на всех входах. Пространственная сложность M — это функция f colonN rightarrowN, где f (n) — максимальное количество ячеек ленты, а M сканирует любой ввод длины M. Если пространственная сложность M равна f (n) , мы можем сказать, что M работает в пространстве f (n) .
Мы оцениваем пространственную сложность машины Тьюринга, используя асимптотические обозначения.
Пусть f colonN rightarrowR+ — функция. Классы сложности пространства могут быть определены следующим образом:
ПРОСТРАНСТВО = {L | L — это язык, определяемый O (f (n)) пространственным детерминистом TM}
ПРОСТРАНСТВО = {L | L — это язык, определяемый недетерминированным TM пространства O (f (n))}
PSPACE — это класс языков, разрешимых в полиномиальном пространстве на детерминированной машине Тьюринга.
Другими словами, PSPACE = U k SPACE (n k )
Теорема Савича
Одной из самых ранних теорем, связанных со сложностью пространства, является теорема Савича. Согласно этой теореме, детерминированная машина может моделировать недетерминированные машины, используя небольшое количество пространства.
Для сложности времени такое моделирование требует экспоненциального увеличения времени. Для сложности пространства эта теорема показывает, что любая недетерминированная машина Тьюринга, которая использует пространство f (n), может быть преобразована в детерминированную ТМ, которая использует пространство f 2 (n) .
Следовательно, теорема Савича утверждает, что для любой функции f colonN rightarrowR+, где f(n) geqslantn
NSPACE (f (n)) ⊆ SPACE (f (n))
Отношения между классами сложности
Следующая диаграмма изображает отношения между различными классами сложности.
До сих пор мы не обсуждали классы P и NP в этом уроке. Это будет обсуждаться позже.