c++ - 反转 C++ 字符串的时间复杂度

Question

我的作业有一个问题，要在 C++ 字符串中反转单词，就地，只有 O(1) 额外的内存。我对 O(1) 额外内存的含义感到困惑。我理解 O(1) 通常意味着什么，无论输入有多大，计算时间都是恒定的，所以我猜我应该只添加一块内存来跟踪单词的反向。有什么建议么？

Answer 1

O(1) 额外内存意味着“最多使用一些恒定的额外内存”。例如，您不能存储字符串的副本，因为这将占用 O(n) 空间，但您可以存储任何恒定数量的额外ints、chars 等。

更一般地说，像“O(1)”或“O(n)”这样的语句不一定指的是运行时。Big-O 表示法是一种描述函数的方式。算法不可能是 O(n)，但它的运行时间可以是 O(n)。一个算法的空间使用同样可以是 O(1)、O(n)、O(2 ⁿ ) 等。

希望这可以帮助！