for循环内使用数组includes方法的时间复杂度问题及优化咨询

你对当前代码的时间复杂度判断存在偏差：设姓名数组长度为n，单个姓名的平均长度为k，用户输入的长度为m，现有实现的时间复杂度为O(n*(k+m))。常规业务场景下，姓名长度、用户输入长度都是个位数的常数，因此实际运行效率接近O(n)，只有当k/m的量级和n接近时才会达到O(n²)的复杂度，绝大多数场景下原代码已经足够好用。

低侵入性优化方案 #

如果不想修改整体逻辑，仅增加两个前置判断就能过滤大量无效计算，性能提升明显：

• 空用户输入直接返回全量姓名数组，跳过遍历逻辑
• 提前判断姓名长度，比用户输入短的姓名不可能包含输入内容，直接跳过匹配步骤
  对应优化代码：

const inputLen = userInput.length
const arr = []
// 空输入直接返回全量，无需遍历
if (inputLen === 0) return names
for (let i = 0; i < names.length; i++) {
  const currName = names[i]
  // 姓名长度短于输入，不可能匹配直接跳过
  if (currName.length < inputLen) continue
  if (currName.includes(userInput)) {
    arr.push(currName)
  }
}

特定场景下的更高性能方案 #

前缀匹配场景 #

如果你的需求是仅匹配姓名开头（比如输入"王"返回所有王姓姓名），可以做两个优化：

1. 把includes替换为startsWith，不需要遍历整个姓名字符串，匹配速度可提升30%~50%
2. 如果姓名数组规模超过10万、查询频次极高，可以预构建前缀树（Trie）做索引：
   • 预构建前缀树仅需在姓名数组更新时执行一次，时间复杂度为O(所有姓名的总字符数)
   • 后续每次查询的时间复杂度为O(m + k)，m为用户输入长度，k为匹配结果的数量，查询效率远高于逐一遍历

任意子串匹配超大规模场景 #

如果需要支持任意位置子串匹配，且姓名数组是静态不常更新的百万级以上规模，可以预构建后缀数组或者后缀自动机做全局索引，查询效率远高于逐一遍历，但实现复杂度较高，非极端场景不推荐使用。

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