Python中元组的时间复杂度

| 关于哈希（字典）和列表也有类似的问题，这里也有很多信息：http://wiki.python.org/moin/TimeComplexity 但是我没有找到有关元组的任何信息。的访问时间

data_structure[i]

通常，链表为O（n）对于字典是〜O（1）元组呢？是链表的O（n）还是数组的O（1）？

已邀请:

4 个回复

列表和元组均为O（1）。它们在道德上都等同于整数索引数组。

列表和元组的索引方式与其他语言中的数组完全相同。简化的解释是，为对象的引用分配了空间，这些引用占用了统一的空间量，任何索引都简单地乘以引用的大小即可获得数组的偏移量。这为列表和元组提供了常量O（1）的访问权限。

从链表中获取项目是O（n），但是Python列表具有基于数组的实现，因此成本为O（1）。元组也使用数组实现，因此它们也为O（1）。

应该是O(1)，因为它实际上只是一个清单。但是对于python列表，我也希望O(1)！您可能想再考虑一下...

要回复问题请先登录或注册