反向字符串的时间和空间复杂度 [英] Reverse string time and space complexity

问题描述

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

I have written different python codes to reverse a given string. But, couldn't able to figure the which one among them is efficient. Can someone point out the differences between these algorithms using time and space complexities?

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

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

有已经有了一些解决方案，但是我找不到时间和空间的复杂性。我想知道 s [::-1] 需要多少空间？

There are already some solutions out there, but I couldn't find out the time and space complexity. I would like to know how much space s[::-1] will take?

推荐答案

即使没有尝试进行基准测试（您也可以轻松实现）， reverse_1 由于许多原因而变得缓慢：

Without even trying to bench it (you can do it easily), reverse_1 would be dead slow because of many things:

• 具有索引的循环


• 不断添加

因此，由于循环&索引， O（n * n）时间复杂性，因为有字符串拷贝， O（n）复杂性，因为它使用了

So, slow because of loop & indexes, O(n*n) time complexity because of the string copies, O(n) complexity because it uses extra memory to create temp strings (which are hopefully garbage collected in the loop).

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

• 不使用可见循环


• 返回字符串不需要从/到列表进行转换


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

您不能在时间上击败它空间复杂度和速度。

So you cannot beat it in terms of time & space complexity and speed.

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

If you want an alternative you can use:

''.join(reversed(s))

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

but that will be slower than s[::-1] (it has to create a list so join can build a string back). It's interesting when other transformations are required than reversing the string.

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

Note that unlike C or C++ languages (as far as the analogy goes for strings) it is not possible to reverse the string with O(1) space complexity because of the immutability of strings: you need twice the memory because string operations cannot be done in-place (this can be done on list of characters, but the str <=> list conversions use memory)

这篇关于反向字符串的时间和空间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！