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

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]？

Answer 1

甚至不尝试reverse_1将其放在板凳上（您可以轻松完成），由于许多原因，速度会很慢：

• 带索引的循环
• 不断地向字符串添加字符，每次创建一个副本。

所以，慢是因为循环和索引，O(n*n)时间复杂度是因为字符串副本，O(n)复杂是因为它使用额外的内存来创建临时字符串（希望在循环中被垃圾收集）。

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

• 不使用可见循环
• 返回一个字符串而不需要从/到列表转换
• 使用来自 python 运行时的编译代码

因此，您无法在时间、空间复杂性和速度方面击败它。

如果你想要一个替代品，你可以使用：

''.join(reversed(s))

但这会比s[::-1]（它必须创建一个列表以便join可以构建一个字符串）慢。当需要其他转换而不是反转字符串时，这很有趣。

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