我认为图灵机的时间复杂度和空间复杂度的定义是相同的，我无法区分 他们之间。
请帮帮我。谢谢。
最佳答案
对于图灵机，时间复杂度衡量的是当机器在某些输入上启动时磁带移动了多少次。空间复杂度是指机器运行时写入磁带的多少个单元格。
TM 的时间复杂度与其空间复杂度有关。特别地，如果 TM 的空间复杂度对于输入 w 是 f(w)，那么它的时间复杂度必须至少是 f(w)，因为磁带必须至少移动 f(w) 步才能写出那么多细胞。此外，如果 TM 具有磁带字母表 Γ 和状态集 Q，那么如果 TM 在输入 w 上的空间复杂度为 f(w) 并且 TM 在 w 上停止，则时间复杂度必须至多为 |Q|Γ f(n)。要看到这一点，请注意 TM 在其执行过程中的任何时刻的配置都由一串 f(n) 个纸带单元组成，每个纸带单元可以包含任何纸带符号，并且可以位于它的任何一个 |Q| 中。州。
如果您查看像 linear bounded automaton 这样的受限图灵机，就会出现这种区别的一个有趣示例。 (LBA)，一种图灵机，其磁带被限制在与输入大小成比例的空间内。尽管 TM 的空间复杂度限制为 O(n)，但任何特定 LBA 的时间复杂度都可以是输入大小的指数。
希望这对您有所帮助!
关于algorithm - 图灵机中的时间复杂度与空间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7137187/