问题描述
我写了不同的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)
这篇关于反向字符串的时间和空间复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!