LeetCode最长公共前缀题嵌套while循环时间复杂度为何是O(S)而非n²

「只要是嵌套循环时间复杂度就一定是O(n²)」是非常典型的认知误区，时间复杂度的核心统计逻辑是所有原子操作的总执行次数，和循环嵌套层数没有必然的对应关系。

对应的解法代码如下：

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++)
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }        
    return prefix;
}

先拆解这段代码的运行逻辑：

• 初始把输入的第一个字符串设为候选公共前缀
• 外层for循环逐个遍历后面的每一个字符串
• 内层while循环做校验：如果当前候选前缀不是当前遍历到的字符串的开头前缀，就把候选前缀的末尾砍掉1位，直到前缀匹配，或者前缀被砍为空直接返回空结果

我们逐部分统计总操作量就能算出复杂度：

• 首先明确S是输入所有字符串的字符总数，也就是数组里每个字符串的长度相加的总和。
• 候选前缀prefix从初始化之后只会变短、不会变长：每执行一次截短操作，前缀长度减1，最多截短到长度为0就直接返回，整个算法运行过程中，截短前缀的操作总次数最多不会超过第一个字符串的长度，存在全局硬上限。
• 大家容易忽略indexOf这个内置方法的开销：Java中字符串的indexOf做前缀匹配时，本质是逐字符比对，单次调用的比对字符数，不会超过当前候选前缀的长度，也不会超过当前被匹配字符串的长度。
• 把所有逐字符比对的次数、所有截短前缀的操作次数加总，总次数永远不会超过所有字符串的字符总数S。举两个极端场景验证：
  • 最坏场景1：输入的所有字符串完全相同。此时每遍历一个字符串，indexOf只需要比对和当前前缀等长的字符，不需要截短前缀，总比对次数刚好等于所有字符串的长度之和，也就是S。
  • 最坏场景2：第一个字符串长度为200，剩下的99个字符串首字符都和第一个字符串不同。此时遍历第二个字符串时，前缀会被逐位砍到空直接返回，总操作数也就200+1，远小于所有字符串的总字符数。

至于为什么不是大家直觉里的O(n²)：O(n²)的嵌套循环成立前提是，外层循环每执行1次，内层循环都要完整执行n次，总操作数是两层循环次数的乘积。但这段代码里的内层while循环有全局的执行次数上限——前缀最多只会被截短第一个字符串的长度那么多次，根本不会出现外层每跑一轮、内层都跑满固定次数的情况，自然不符合O(n²)的复杂度特征。

内容的提问来源于stack exchange，提问作者garfield the cat