c++ - 在 c++ 中反转 c 字符串的最快方法是什么？

Question

仅使用库在 c++ 中反转 c 字符串的最快方法是什么？特别是，是否有任何方法需要少于 O(strlen) 时间？

Answer 1

不可能有一种方法可以n在短时间内反转一个长度的字符串O(n)。根据“反转”的定义，每个字符都必须至少读取一次。

Answer 2

我怀疑它的复杂性低于 O(N) 是可能的。鉴于 C 字符串的定义方式（NUL 终止），您甚至无法找到复杂度低于 O(N) 的字符串的最终元素，因此很难想象实际上用它做任何复杂度较低的事情。

至于你如何做到这一点，通常是将第一个元素与最后一个元素交换，第二个元素与倒数第二个元素交换，依此类推。

要实现比线性更快的目标，您可能需要从存储字符串的长度开始。然后，您将（例如）设置一个标志以指定从末尾开始，而不是实际反转它。这将允许恒定的复杂性“逆转”。这在 C++ 中相当容易管理，您可以在其中“保护”存储，并重载运算符以提供所需方向的访问。

Answer 3

没有比 O(n) 更好的时间了，因为你必须至少触摸每个字符一次。

所以像：

void reverseString (char *s) {
    char t, *d = &(s[strlen (s) - 1]);
    while (d > s) {
        t = *s;
        *s++ = *d;
        *d-- = t;
    }
}

可能与您在标准 C++ 中的效率一样高。

现在有一些方法可以改善这一点，如果你被允许强加额外的信息，你可以根据你的访问模式将成本摊销到小于 O(n) 的程度。

我的意思是在原始字符串中保留一个反向字符串和脏标志。

• 如果您在标志脏时尝试访问反转的字符串，请计算反转，将标志设置为清除并返回计算/存储的反转。成本是 O(n)。
• 如果您在标志干净时尝试访问反转的字符串，只需返回计算/存储的反转。成本是 O(1)。
• 如果您更改了原始字符串，请将标志设置为脏。成本是 O(1)。

如果您访问反向字符串的频率高于更改原始字符串的频率，则成本会低于简单的“每次计算反向字符串”方法。