矩阵内单词搜索回溯算法的运行时复杂度分析及争议探讨

最终渐近复杂度结论为：O(m * n * 3^l)，其中l为目标字符串s的长度，此前争议的访问状态校验、方向遍历判断等固定操作，并不会改变这一复杂度上界。

核心推导逻辑 #

• 首先拆解外层两层循环的工作量：双重循环遍历全部m * n个网格单元，仅对匹配s首字符的单元触发一次search递归调用，这部分的固定开销是O(m * n)。
• 再拆解单起点触发的search递归开销：
  • 每次递归进入search时，需要完成固定量的常数级操作：判断当前匹配深度是否达到s的长度、遍历4个候选方向、做坐标边界校验、查布尔访问数组visited确认节点是否已走过、匹配对应位置的字符——这些操作单步耗时都是常数，不会随输入规模线性增长。
  • 递归路径的增长边界：从起点出发后，每走一步就会把当前坐标标记为已访问，因此下一层可探索的方向最多3个（排除上一步来源的方向），深度为l的所有可能自避免探索路径总数的上界为4 * 3^(l-1)，和3^l完全同阶。
• 你提到的递推展开中的固定校验开销，本质上就是每一层递归的常数操作累加：对长度为l的递归树，所有节点的固定操作总开销为等比数列求和结果4 * (1 + 3 + 3^2 + ... +3^(l-1)) = 2 * (3^l - 1)，这个量级和3^l完全同阶，会被大O记号吸收到常数系数中，不会产生独立的增长项。

常见认知误区澄清 #

• 误区1：认为“漏算访问状态校验的操作，所以原复杂度分析不成立”——大O渐近复杂度的核心是刻画增长量级，只要单节点的操作是常数级，不管是每次做3次方向判断还是5次判断，都不会改变O(3^l)的上界，所谓的“漏算开销”从来没有跳出这个量级的范围。
• 误区2：认为引入visited数组后复杂度会和网格总规模m * n绑定——实际递归路径的最大长度就是s的长度l，只要l < m * n，复杂度始终由3^l主导；如果l >= m * n，算法本身不可能找到合法匹配，会直接终止，复杂度为O(m * n)。
• 误区3：认为递推式中第一层的4个方向会带来量级提升——4 * 3^(l-1)和3^l的比例是固定常数，完全属于同阶，不存在量级差异。

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