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

小编典典

algorithm

我写了不同的python代码来反转给定的字符串。但是，无法确定其中哪一个是有效的。有人可以指出使用时间和空间复杂度的这些算法之间的区别吗？

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

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

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

阅读 432

2020-07-28

共1个答案

小编典典

甚至没有尝试进行测试（您可以轻松实现），reverse_1由于许多原因，它的运行速度会非常缓慢：

因此，由于循环和索引而导致速度较慢，由于O(n*n)字符串复制而导致时间复杂，O(n)由于使用额外的内存来创建临时字符串（希望在循环中进行垃圾回收）而导致了复杂性。

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

因此，您不能在时间和空间复杂性以及速度方面击败它。

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

''.join(reversed(s))

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

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

2020-07-28