图灵机中的时间复杂度与空间复杂性

Question

我认为图灵机的时间复杂性和空间复杂性的辩护是相同的,我无法区分它们.

请帮我.谢谢.

Answer 1

对于图灵机,时间复杂度是在某些输入上启动机器时磁带移动的次数的度量.空间复杂度是指机器运行时写入磁带的单元格数.

TM的时间复杂度与其空间复杂性有关.特别是,如果TM的tue空间复杂度对于输入w是f(w),则其时间复杂度必须至少为f(w),因为磁带必须至少移动f(w)步骤以写出许多细胞.另外,如果TM具有磁带字母Γ和状态Q的集合,那么如果输入w上的TM的空间复杂度是f(w)并且TM在w上停止,则时间复杂度必须至多为| Q |Γ ^f(n).要看到这一点,请注意TM在其执行中的任何一点的配置都包含一串f(n)个磁带单元,每个磁带单元可以包含任何磁带符号,并且可以位于其中任何一个| Q |中.状态.

如果你看一下受限制的图灵机,如线性有界自动机(LBA),这是一种图灵机,它的磁带被限制在与输入大小成比例的空间,就会出现一个有趣的例子.尽管TM的空间复杂度限于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无关.