元组中访问元素的时间复杂度
这里有一个关于哈希（字典）和列表的类似问题，还有一些很好的信息可以参考：http://wiki.python.org/moin/TimeComplexity
不过我没有找到关于元组的相关内容。
访问时间方面：
data_structure[i]
- 链表的访问时间通常是 O(n)
- 字典的访问时间大约是 O(1)
那元组呢？它的访问时间是 O(n)，像链表一样，还是 O(1)，像数组一样呢？
4 个回答
3
从链表中获取一个项目的时间复杂度是O(n)，这意味着如果链表里的元素越来越多，获取一个元素所需的时间也会相应增加。
而Python的列表是基于数组实现的，所以从中获取一个元素的时间复杂度是O(1)，也就是说，无论列表有多长，获取一个元素所需的时间都是固定的。
元组也是用数组来实现的，所以获取元组中的元素同样是O(1)。
4
列表和元组的索引方式和其他语言中的数组是一样的。
简单来说，就是为对象的引用分配了空间，这些引用占用的空间是固定的。要找到某个索引的位置，只需要把索引值乘以引用的大小，就能得到在数组中的位置。这让我们可以以固定的时间（O(1)）访问列表和元组。
11
对于列表和元组来说，它们的访问时间都是O(1)。这意味着无论你要访问哪个元素，所需的时间都是一样的，就像用数字索引的数组一样。