我编写了不同的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))
但这将比CCD_ 6慢(它必须创建一个列表以便CCD_。当除了反转字符串之外还需要其他转换时，这很有趣。
请注意，与C或C++语言不同(就字符串而言(，由于字符串的不变性，不可能用O(1)空间复杂性来反转字符串：您需要两倍的内存，因为字符串操作无法就地完成(这可以在字符列表上完成，但str<=>list转换使用内存(