DFS中数组与集合实现visited的时间复杂度差异探究

• 内存访问效率天差地别
  二维数组是连续的内存块，CPU缓存可以预加载相邻元素，访问时缓存命中率极高，几乎是直接从缓存取数据。而集合存储的(row, col)元组分散在内存各处，每次查询都是随机内存访问，缓存完全派不上用场，单次访问耗时比数组索引高得多。

• 哈希操作的额外开销
  用集合判断元素是否存在时，首先要对(row, col)元组计算哈希值，这个过程本身就有计算成本。而且哈希表难免出现冲突，需要额外的比较步骤确认元素是否真的在集合里。而二维数组直接通过索引定位，只是简单的算术运算（比如row * 列数 + col），没有任何额外操作。

• 底层实现的常数时间差异
  虽然理论上两者查询时间都是O(1)，但“常数时间”的实际耗时差了好几个数量级。二维数组的索引访问是硬件级别的高效操作，而集合的哈希表需要维护桶结构、处理扩容等逻辑，单次查询的常数开销远大于数组。对于DFS这种需要频繁判断访问状态的场景，成千上万次查询的时间差累计起来，就会突破题目时间限制。

• 语言层面的优化差距
  拿Python举例，列表（二维数组）的索引访问是底层C实现的原生操作，速度极快；而集合的in操作虽然也是C实现，但涉及哈希计算、冲突处理等复杂逻辑，比单纯的索引访问慢很多。当题目中的地图规模较大时，这种性能差距会被直接放大，导致超时。

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