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

Question

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

请帮我。谢谢。

Answer 1

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

TM 的时间复杂度与其空间复杂度有关。特别是，如果输入 w 的 TM 的 tue 空间复杂度为 f(w)，那么它的时间复杂度必须至少为 f(w)，因为磁带必须移动至少 f(w) 步才能写出那么多细胞。此外，如果 TM 具有带字母 Γ 和状态集 Q，那么如果 TM 在输入 w 上的空间复杂度为 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无关。