我认为图灵机的时间复杂度和空间复杂度的定义是相同的，我无法区分
它们之间。
请帮我。谢谢。
对于图灵机，时间复杂度是当机器根据某些输入启动时磁带移动的次数的度量。空间复杂度是指机器运行时写入磁带的单元数。
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 f(n)|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 with the tape head in any of the f(n) positions.
如果你看看受限图灵机，比如线性有界自动机 http://en.wikipedia.org/wiki/Linear_bounded_automaton（LBA），一种图灵机，其磁带限制于与输入大小成比例的空间。尽管 TM 的空间复杂度限制为 O(n)，但任何特定 LBA 的时间复杂度都可以是输入大小的指数。
希望这可以帮助！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
