含IndexOf与Substring的While循环时间复杂度分析咨询

前置假设与前提 #

基于你描述的代码逻辑（循环截取word首字符直至prefix出现在开头），结合Java官方实现的时间复杂度定义：

• indexOf(String str)：最坏时间复杂度为O(N*M)（N为当前word长度，M为prefix长度），最佳情况为O(M)（首字符不匹配或完全匹配）
• substring(int beginIndex)（Java 7+）：时间复杂度为O(N)（需复制剩余字符数组，N为当前word长度）

核心问题解答 #

1. 四个场景的复杂度分析验证 #

场景1：prefix与word完全相同，循环执行0次

分析正确。此时仅执行1次indexOf，因完全匹配属于indexOf最佳情况，仅需遍历M个字符即可确认匹配，无循环操作，总复杂度为O(M)。

场景2：prefix与word仅首字符匹配，IndexOf执行M次，Substring执行M-1次

分析不准确。假设初始word长度N≥M：

• 每次循环后word长度递减1，第k次循环时word长度为N - k
• 每次indexOf因仅首字符匹配，需遍历到word末尾才能确认不匹配，单次最坏时间为O((N - k)*M)
• M次indexOf总时间为：$\sum_{k=0}^{M-1} O((N - k)M) = O(NM^2)$
• M-1次substring总时间为：$\sum_{k=0}^{M-2} O(N - k) = O(M*N)$
• 总复杂度应为O(N*M²)，而非你判定的O(N*M + M²)

场景3：prefix存在但不在word开头

你的纠结点未命中核心复杂度范围：
假设prefix首次出现在word的第k个位置（k≥1，从0开始计数），循环需执行k次：

• indexOf总时间：首次查找为O(NM)，后续k次查找的word长度依次递减，总时间为$O(Mk*(2N -k +1)/2)$
• substring总时间：k次操作的总时间为$O(k*(2N -k +1)/2)$
• 若k接近N（比如prefix在word末尾），总复杂度会达到O(N²*M)，远高于你纠结的O(NM + M²)或O(N² + M²)；仅当k远小于N时，复杂度才会趋近于O(NM)。

场景4：IndexOf最坏场景，判定复杂度为O(N*M)

分析不准确。若仅指单次indexOf的最坏情况，确实为O(NM)，但结合循环来看，最坏情况是每次indexOf都需遍历到word末尾确认不匹配，且循环执行多次（如场景3中k接近N的情况），此时总复杂度会远高于O(NM)。

2. 场景2是否为该代码的最坏复杂度？ #

不是。
场景2的循环次数最多为M次（当word长度减到小于M时停止），但如果prefix存在于word末尾位置（k=N-M），循环需执行k=N-M次：

• indexOf总时间约为$O(N²*M)$
• substring总时间约为$O(N²)$
  总复杂度为O(N²M)，当N>M时，这比场景2的O(NM²)复杂度更高，才是真正的最坏情况。

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