字符串首个重复字符查找O(n)算法运行时间疑问

你的疑问本质是对算法所用数据结构的时间复杂度认知偏差，和计算模型的适用场景问题，具体解答如下：

两种算法的核心差异 #

• 朴素O(n²)实现：每遍历到一个新字符，就倒序遍历所有已经扫描过的前缀字符逐一比对，最坏情况（无重复字符）下总比对次数为等差数列求和，即n(n-1)/2，时间复杂度为O(n²)。
• 你提到的O(n)实现，核心是采用了支持O(1)平均/最坏时间成员查询的数据结构，不需要遍历所有历史字符，常见实现分两类：
  1. 有限字符集场景：比如输入仅包含ASCII字符，直接开辟一个长度等于字符集大小的布尔数组seen，初始值全为false。每遍历到字符c时，直接以c的编码值为下标访问seen[c]：若为true说明之前出现过，直接返回当前字符；若为false则将seen[c]赋值为true。数组的随机访问是常数时间操作，不存在遍历逻辑。
  2. 不限字符集场景：用哈希集合（Hash Set）存储已出现的字符，哈希表的平均插入、查询时间复杂度为O(1)，内部通过哈希映射直接定位元素位置，不需要遍历所有已存储的历史字符。

关于计算模型的问题解答 #

你提到的和图灵机的关联确实存在：

• 我们日常算法分析默认采用RAM（随机存取机）计算模型，该模型假设固定大小数据的随机内存访问、算术运算、比较操作都为常数时间，在这个模型下上述O(n)的结论完全成立，也是工业界通用的复杂度判定标准。
• 如果你采用单带图灵机作为计算模型，那么数组随机访问、哈希表查询都无法做到严格O(1)，不过该模型基本仅用于理论计算复杂度研究，日常工程场景和常规算法题分析都不会采用。

内容的提问来源于stack exchange，提问作者Hans-Ulrich Rudel