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

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

甚至没有尝试进行测试（您可以轻松实现），

reverse_1

由于许多原因，它的运行速度会非常缓慢：

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

因此，由于循环和索引而导致速度较慢，由于

O(n*n)

字符串复制而导致时间复杂，

O(n)

由于使用额外的内存来创建临时字符串（希望在循环中进行垃圾回收）而导致了复杂性。

另一方面

s[::-1]

：

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

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

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

''.join(reversed(s))

但这会比

s[::-1]

（必须创建一个列表，以便

join

可以重新构建一个字符串）慢。当需要其他转换而不是反转字符串时，这很有趣。

请注意，与C或C ++语言不同（就字符串的类推而言） ， 由于字符串

O(1)

的 不可变性 ， 不可能
以空间复杂性来反转字符串：您需要两倍的内存，因为字符串 *** 作无法就地完成（这可以在字符列表上完成，但是

str

<=>

list

转换使用内存）