Python中元组的时间复杂性

Question

关于hash（字典）和列表有类似的问题，这里也有一条很好的信息：http://wiki.python.org/moin/TimeComplexity

但我没有找到元组的任何信息。在

的访问时间

data_structure[i]

• 因为链表一般是O（n）
• 因为字典是~O（1）

元组呢？ 对于链表来说是O（n）类还是数组的O（1）样？在

Answer 1

列表和元组都是O（1）。它们在道义上都相当于一个整数索引数组。在

Answer 2

从链表中获取一个项目是O（n），但是Python列表有基于数组的实现，因此成本是O（1）。在

元组也是使用数组实现的，所以对它们也是O（1）。在

Answer 3

列表和元组的索引方式与其他语言中的数组完全相同。在

一个简单的解释是空间被分配给对对象的引用，这些引用占用统一的空间量，任何索引都只需乘以引用的大小，就可以得到数组中的偏移量。这给了常量O（1）访问列表和元组。在