Сложность времени и сложность пространства в машинах Тьюринга

Question

Я думаю, что определения сложности времени и сложности пространства для машин Тьюринга идентичны, и я не могу их дифференцировать между ними.

Пожалуйста, помогите мне. Спасибо.

Answer 1

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

Временная сложность ТМ связана с его пространственной сложностью. В частности, если сложность пространства ТМ равна f (w) для ввода w, то ее временная сложность должна составлять не менее f (w), поскольку лента должна переместить как минимум f (w) шагов, чтобы записать столько клетки. Кроме того, если у ТМ есть ленточный алфавит & Гамма; и набор состояний Q, тогда, если пространственная сложность ТМ на входе w равна f (w) и ТМ останавливается на w, временная сложность должна быть не более | Q | & Gamma; ^{f (n)} . Чтобы увидеть это, обратите внимание, что конфигурация TM в любой точке ее выполнения состоит из строки из f (n) ячеек ленты, каждая из которых может содержать любой символ ленты и может находиться в одном из его | Q | состояния.

Интересный пример этого различия появляется, если вы посмотрите на ограниченные машины Тьюринга, такие как линейный ограниченный автомат (LBA), машина Тьюринга, чья лента ограничена пространством, пропорциональным размеру входных данных. Хотя сложность пространства ТМ ограничена O (n), временная сложность любого конкретного LBA может быть экспоненциальной по размеру входных данных.

Надеюсь, это поможет!

Answer 2

Сложность времени - это мера , сколько времени алгоритм требует для получения ответа.

Сложность пространства - это мера сколько памяти алгоритм использует в процессе.

В качестве примера рассмотрим задачу вычисления суммы целых чисел 1 .. n .Простой алгоритм будет работать примерно так:

procedure sum(n)
  total := 0
  for i = 1 to n
    total := total + a[n]
  return total

Временная сложность этого алгоритма составляет O ( n ), потому что цикл явно проходит n итераций.С другой стороны, сложность пространства равна O (1), потому что единственная память, которая нам нужна, это total и i , которые не зависят от n .