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

有关列表复杂度的问题

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

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

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

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

你确定你看到的是对的吗？
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)
页: [1]
查看完整版本: 有关列表复杂度的问题