重复字符串的图灵机的时间复杂度

Question

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

现在我的想法是，

• 1磁带确定性的机器需要为O（n^2）找到中点（反复穿越出在输入第一个和最后一个符号）和O （n^2）来比较第一半和第二半（因为它必须来回n/2次，每次都要经过n/2的字符串），

• 2带TM取O （n^2）找到中点，O（n）将第二部分复制到第二个磁带上，然后O（n）同时比较两部分，

• 而非确定性猜测中点并用O（n^2）来比较这两个半部分。

不过，我觉得这三种情况下不应该都有的O相同的时间复杂度（N^2），所以在想，如果我的推理是不正确的地方（或我是否正确，只是想得多关于这个问题）。任何输入将不胜感激！

Answer 1

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

所以你对他们都是正确的。他们都是O（n^2）。这是录音带走上恐龙活跃工作之路的一个原因。对于备份，它们仍然在某些地方使用，但这是因为它们对于线性存储仍然只有O（n）。