Python中集合in操作与列表索引的时间复杂度差异探究

• 核心差异：底层实现的操作开销
  你用的长度为26的列表本质是连续内存的数组结构，访问时通过字母到0-25下标的映射（比如ord(c) - ord('A')）直接定位元素，这是CPU级别的内存地址偏移操作，没有额外逻辑，常数开销极小，是真正的O(1)操作。
  而Python的set虽然平均查询复杂度是O(1)，但底层基于哈希表实现，每次c in set操作都要经历：

  1. 计算字符的哈希值；
  2. 对哈希值取模定位到哈希表的对应桶；
  3. 遍历桶内元素完成相等性校验（哪怕无冲突也需这一步）；
     这些步骤的常数开销远大于列表的直接索引，在DFS这种递归次数极多、每步都要多次判断的场景下，累积的时间差会直接导致超时。

• 哈希冲突不是主要原因
  对于26个大写英文字母，Python的哈希函数设计能保证它们的哈希值均匀分布，几乎不会出现冲突。但即便没有冲突，集合查询的上述三步开销，在高频调用下的累积效应依然显著。

• 内存局部性的隐性影响
  列表的元素是连续存储的布尔值/整数，CPU缓存的命中率极高；而集合的元素是分散的哈希表节点，内存地址不连续，缓存命中率低，这也会进一步拉大两者的执行时间差距。

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