Python中__getitem__时间复杂度及[-1]索引跨容器访问复杂度问询

1. __getitem__方法的时间复杂度 #

__getitem__是Python容器类实现下标访问的魔法方法，没有统一的时间复杂度，完全由对应容器的底层实现决定：

• 支持随机访问的顺序存储容器（列表、元组、字符串）：__getitem__时间复杂度为O(1)
• 哈希表实现的容器（字典、集合）：按键查询的__getitem__平均时间复杂度为O(1)，最坏情况为O(n)
• 链式存储的非随机访问容器（如单链表实现的队列）：__getitem__时间复杂度为O(n)

2. [-1]索引访问末尾元素的时间复杂度及不同容器差异 #

Python处理负索引时，会先将负索引转换为正索引：转换后的正索引 = 容器长度 + 负索引，转换逻辑本身是O(1)，后续访问逻辑和同位置正索引完全一致，不同内置容器的表现如下：

• 列表（list）、元组（tuple）：二者底层都是连续内存的顺序存储结构，支持随机访问，转换后的正索引可直接通过内存偏移量定位元素，因此[-1]访问末尾元素的时间复杂度为O(1)，二者表现一致。
  你提供的测试代码可正常运行，注意不要用list作为变量名，会覆盖Python内置的列表类，修正后示例：

  my_list = [1,2,3]
  print(my_list[-1])
  # 输出：3
  

• 字典（dict）：首先字典的[]运算符接收的是键，而非位置偏移量，不存在用[-1]取末尾元素的用法：
  • Python 3.7之前的版本字典无序，本身就没有“末尾元素”的定义，使用[-1]会直接抛出KeyError（除非你主动存入了键为-1的键值对）
  • Python 3.7及以上版本字典按插入顺序有序，也无法通过[-1]直接取最后插入的元素，只能通过next(reversed(dict.keys()))这类语法获取，该操作时间复杂度为O(1)，但不属于[-1]索引的使用场景。

综上，列表和元组用[-1]取末尾元素复杂度一致，字典无法通过该语法取末尾元素，三者不存在一致的复杂度表现。

内容的提问来源于stack exchange，提问作者amirhossein