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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

def reverse_1(s):
      result = ""
      for i in s : 
          result = i + result
      return result
def reverse_2(s): 
      return s[::-1]

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

回答：

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

  • 与索引循环

  • 不断在字符串中添加字符，每次都创建一个副本。

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

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

  • 不使用可见循环

  • 返回一个字符串，而无需从/到列表进行转换

  • 使用来自python运行时的编译代码

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

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

''.join(reversed(s))

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

请注意，与C或C ++语言不同（就字符串的类推而言） 由于字符串O(1)的 不可变性 ，

以空间复杂性来反转字符串：您需要两倍的内存，因为字符串操作无法就地完成（这可以在字符列表上完成，但是str<=> list转换使用内存）

以上是 反向字符串的时间和空间复杂度 的全部内容， 来源链接： utcz.com/qa/401754.html

回到顶部