栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

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

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

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

甚至没有尝试进行测试(您可以轻松实现),

reverse_1
由于许多原因,它的运行速度会非常缓慢:

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

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

O(n*n)
字符串复制而导致时间复杂,
O(n)
由于使用额外的内存来创建临时字符串(希望在循环中进行垃圾回收)而导致了复杂性。

另一方面

s[::-1]

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

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

如果您想要替代方法,可以使用:

''.join(reversed(s))

但这会比

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

请注意,与C或C ++语言不同(就字符串的类推而言) 由于字符串

O(1)
不可变性不可能
以空间复杂性来反转字符串:您需要两倍的内存,因为字符串操作无法就地完成(这可以在字符列表上完成,但是
str
<=>
list
转换使用内存)



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/427685.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号