[已解决]有关列表复杂度的问题

素手就琴 · 发表于 2020-4-8 09:13:59

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

想请教一下为什么python里面的列表的index函数的时间复杂度是O（1）呢

最佳答案

月排行榜 / 总排行榜

sunrise085

2020-4-8 09:42:37

你确定你看到的是对的吗？
python 中 list各个函数的时间复杂度要看其执行代码
你所说的index好像是list[ｉ]吧？很多地方把直接拿下标索引也称之为index，但这不是index函数，这种方式的时间复杂度是O（1），因为其位置是可以直接得到的，然后就直接获取该元素了。
而list.index()的时间复杂度是O（n），因为它需要遍历一次列表，最坏的情况是一直找到最后一个元素，因此其时间复杂度为O（n）

跳转到最佳答案楼层

qiuyouzhi · 发表于 2020-4-8 09:18:04

你去看它怎么写的不就好了

sunrise085 · 发表于 2020-4-8 09:42:37

这个最佳答案由 sunrise085 给出，感谢 sunrise085 的回答。

单击隐藏图章

你确定你看到的是对的吗？
python 中 list各个函数的时间复杂度要看其执行代码
你所说的index好像是list[ｉ]吧？很多地方把直接拿下标索引也称之为index，但这不是index函数，这种方式的时间复杂度是O（1），因为其位置是可以直接得到的，然后就直接获取该元素了。
而list.index()的时间复杂度是O（n），因为它需要遍历一次列表，最坏的情况是一直找到最后一个元素，因此其时间复杂度为O（n）

zltzlt · 发表于 2020-4-8 12:59:03

并不是，你在哪里看到的？list.index() 的时间复杂度是 O(n)，不是 O(1)，下标访问列表的时间复杂度才是 O(1)

账号		自动登录	找回密码
密码			立即注册