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

Question

我认为图灵机的时间复杂度和空间复杂度的定义是相同的，我无法区分 他们之间。

请帮助我。谢谢。

Answer 1

对于图灵机，时间复杂度是衡量机器在某些输入上启动时磁带移动了多少次。空间复杂度是指机器运行时写入磁带的多少个单元。

TM 的时间复杂度与其空间复杂度相关。特别是，如果对于输入 w，TM 的空间复杂度为 f(w)，那么它的时间复杂度必须至少为 f(w)，因为磁带必须移动至少 f(w) 步才能写出这么多细胞。此外，如果 TM 具有磁带字母 Γ 和状态集 Q，则如果 TM 在输入 w 上的空间复杂度为 f(w) 并且 TM 在 w 上停止，则时间复杂度必须至多为 f(n) |Q|γ^f(n)。要看到这一点，请注意 TM 在其执行过程中任何点的配置都由一串 f(n) 个磁带单元组成，每个磁带单元都可以包含任何磁带符号，并且可以位于其任何 |Q| 之一中。磁带头处于任何 f(n) 位置时的状态。

如果您查看像“线性有界自动机”（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。