时间复杂度与空间的图灵机的复杂性 [英] Time complexity versus space complexity in Turing machines

问题描述

我觉得时间复杂度和空间复杂度图灵机defenitions是相同的，我不能区分 他们之间。

I think defenitions of time complexity and space complexity for Turing machines are identical and I can't differentiate between them.

请帮助我。谢谢你。

推荐答案

通过关于图灵机，时间复杂度是多少次磁带转动，当机器上启动某些输入的量度。空间复杂性是指如何磁带许多细胞被写入机器运行时

With regards to a Turing machine, time complexity is a measure of how many times the tape moves when the machine is started on some input. Space complexity refers to how many cells of the tape are written to when the machine runs.

一个TM的时间复杂被连接到它的空间的复杂性。特别是，如果周二空间中的TM的复杂性为f（w）的输入瓦特，那么其时间复杂度必须至少为F（w）的，由于带具有移动至至少F（w）的步骤，以写出许多细胞。此外，如果商标拥有带字母和伽玛;并设置的状态Q，则若TM的空间复杂度上的输入瓦特为f（w）的和TM停止上瓦特，时间复杂性必须至多| Q |＆伽玛; ^F（N）。看到这一点，请注意，对TM的在其执行的任何点的配置由F（N）胶带细胞，其每一个可以包含任何带符号的字符串，并且可以在其任何1 | Q |状态。

The time complexity of a TM is connected to its space complexity. In particular, if tue space complexity of a TM is f(w) for input w, then its time complexity must be at least f(w), since the tape has to move at least f(w) steps to write out that many cells. Additionally, if the TM has tape alphabet Γ and set of states Q, then if the space complexity of the TM on an input w is f(w) and the TM halts on w, the time complexity must be at most |Q|Γ^f(n). To see this, note that the configuration of the TM at any point in its execution consists of a string of f(n) tape cells, each of which can contain any tape symbol, and can be in one of any of its |Q| states.

这种区别的一个有趣的例子，如果你限制的图灵机像线性有界自动机（LBA），图灵机具有其磁带限于空间正比于输入的大小。虽然对TM的空间复杂度被限制为O（n），任何特定的LBA的时间复杂度可以指数在输入的大小。

An interesting example of this distinction appears if you look at restricted Turing machines like the linear bounded automaton (LBA), a Turing machine that has its tape restricted to space proportional to the size of the input. Although the TM's space complexity is restricted to O(n), the time complexity of any particular LBA can be exponential in the size of the input.

希望这有助于！

这篇关于时间复杂度与空间的图灵机的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！