我的作业中遇到一个问题，即仅使用 O(1) 额外内存就地反转 C++ 字符串中的单词。我对 O(1) 额外内存的含义感到困惑。我理解 O(1) 通常意味着什么，无论输入有多大，计算时间都是恒定的，所以我猜我应该只添加一 block 内存来反向跟踪单词。有什么建议吗？
最佳答案
O(1) 额外内存意味着“最多使用一些常量额外内存”。例如，您无法存储字符串的拷贝，因为这将占用 O(n) 空间，但您可以存储任意恒定数量的额外 int、char 等
更一般地说，像“O(1)”或“O(n)”这样的语句不一定指的是运行时。 Big-O 表示法是一种描述函数的方法。算法不可能是 O(n)，但其运行时间可以是 O(n)。算法的空间使用量同样可以是 O(1)、O(n)、O(2n) 等。
希望这有帮助!
关于c++ - 反转 C++ 字符串的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19215969/