4

我试图找出在三种情况下接受重复字符串（ww）的图灵机的时间复杂度：1 磁带确定性机器、2 磁带确定性机器和 1 磁带非确定性机器。

现在我的想法是

  • 1-tape 确定性机器需要 O(n^2) 来找到中点（通过重复删除输入中的第一个和最后一个符号）和 O(n^2) 来比较前半部分和后半部分（因为它必须来回 n/2 次，每次通过 n/2 的字符串），

  • 2-tape TM 需要 O(n^2) 找到中点，O(n) 将后半部分复制到第二个磁带，然后 O(n) 同时比较两半，

  • 而不确定的人猜测中点并取 O(n^2) 来比较两半。

但是，我觉得这三种情况不应该都具有相同的 O(n^2) 时间复杂度，所以想知道我的推理是否在某个地方不正确（或者我是否正确并且只是在思考这个问题）。任何输入将不胜感激！

4

1 回答 1

0

在使用磁带时，这个逻辑似乎是正确的。在磁盘或固态驱动器上，更适合以非线性方式访问数据的不同算法将具有较低的 big-O。

所以你对所有这些都是正确的。它们都是 O(n^2)。这是磁带在积极工作方面走上了恐龙之路的原因之一。对于备份，它们仍然在某些地方使用，但那是因为它们仍然只有 O(n) 用于线性存储。

于 2015-04-21T19:17:38.910 回答