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

Question

我试图找出在三种情况下接受重复字符串 (ww) 的图灵机的时间复杂度:1-tape 确定性机器、2-tape 确定性机器和 1-tape 不确定性机器。

现在我的想法是

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) 时间复杂度，所以想知道我的推理是否在某处不正确(或者我是否正确并且只是想了很多问题)。任何输入将不胜感激!

Answer 1

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

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