反转字符串的时间和空间复杂度

Question

我已经写了不同的Python代码来反转给定字符串。但是，无法确定哪一个算法更有效。有人能够通过时间和空间复杂度指出这些算法之间的差异吗？

def reverse_1(s):
      result = ""
      for i in s : 
          result = i + result
      return result

def reverse_2(s): 
      return s[::-1]

虽然已经有一些解决方案，但我无法找到时间和空间复杂度。 我想知道s [::-1]需要多少空间？

- Venkata Gogu

---

reverse_1 是你可能编写的最糟糕的反转程序，其复杂度为 O(n*2)。请使用第二个复杂度为 O(n) 且不使用循环的程序。 - Jean-François Fabre

但是，如果面试官不接受这种方法，那不就有点作弊了吗？在Python中还有其他反转字符串的方法吗？ - Venkata Gogu

一个快速测试的建议是使用ipython控制台中的timeit功能。这样做：timeit reverse_1('blabla')。 - Lorran Sutter

@smac89 reverse_1 更糟糕：它是 O(n*n)。如果在一个非常大的字符串上尝试，它永远不会结束，因为它必须复制该字符串。所以基本上是 n*(n-1)//2 次复制。 - Jean-François Fabre

我非常希望这个问题不是重复的（我已经回答了它），但如果你阅读其他问题的答案，你会发现我的答案只是总结了这里所说的内容，并得出了相同的结论。也许你可以编辑一下，解释为什么它不是重复的。我非常希望重新打开，但我觉得现在不合适。 - Jean-François Fabre

Answer 1

即使不试图对其进行基准测试（您可以轻松地完成此操作），由于许多原因，reverse_1 的速度会非常慢：

• 使用索引循环
• 不断将字符添加到字符串中，每次都创建一个副本。

因此，由于循环和索引的缘故，reverse_1 很慢，由于字符串复制，时间复杂度为O(n*n)，由于使用额外的内存来创建临时字符串（这些字符串在循环中应该被垃圾回收），因此时间复杂度为O(n)。

另一方面，s[::-1]：

• 不使用可见循环
• 无需从/转换为列表即可返回字符串
• 使用Python运行时的编译代码

因此，无论是时间和空间复杂度还是速度，您都无法击败它。

如果您想要替代方案，您可以使用：

''.join(reversed(s))

但是这比s[::-1]慢（因为它需要创建一个列表，以便join可以构建回字符串）。当需要进行与字符串翻转不同的其他转换时，它会变得有趣。

请注意，与C或C++语言（就字符串而言）不同，由于字符串的不可变性，不可能通过O(1)的空间复杂度来反转字符串：你需要两倍的内存，因为字符串操作无法原地完成（这可以在字符列表上完成，但是str <=> list的转换将使用内存）

- Jean-François Fabre

---

你能否在这些算法之间发布一些答案，例如 O(n) 或 O(logn) ... - Venkata Gogu

这里不可能有O(log(n))的复杂度。最好情况下显然是O(n)。 - Jean-François Fabre

有没有一种方法可以在O(n)时间和O(1)空间内完成这个任务。 - Venkata Gogu

在字符列表中是可能的，但不适用于字符串。 - Jean-François Fabre