关于countPrefixSuffixPairs函数时间复杂度的疑问

你好呀！你的疑惑完全正确——这段代码的时间复杂度确实不是单纯的O(n²)，而是O(n² * m)，其中m代表列表中字符串的平均长度（更准确地说，是所有作为前缀/后缀被检查的words[i]的平均长度）。

咱们来拆解一下原因：

• 首先，嵌套循环部分确实会执行O(n²)次迭代（准确来说是n*(n-1)/2次，属于O(n²)量级）。
• 但每次迭代里的startswith()和endswith()方法并不是常数时间操作：
  • words[j].startswith(words[i])需要逐个比对words[j]的前len(words[i])个字符和words[i]的所有字符，这个过程的时间复杂度是O(k)，k就是words[i]的长度。
  • 同理，words[j].endswith(words[i])需要比对words[j]的最后k个字符，同样是O(k)的时间。
• 把所有迭代的时间开销加起来，总的时间复杂度就会是O(n² * m)，这里m是所有words[i]的平均长度。

举个极端的例子：如果列表里所有字符串都是长度为M的完全相同的字符串，那么每次startswith和endswith都要做M次字符比对，总操作次数就是n²M，显然符合O(n²M)的复杂度。当然，如果某些words[j]的长度比words[i]短，这两个方法会直接返回False，开销很小，但时间复杂度分析通常以最坏情况为准，所以最终复杂度还是O(n²*m)。

附上你提供的代码供参考：

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        n = len(words)
        count = 0
        for i in range(n):
            for j in range(i+1, n):
                if words[j].startswith(words[i]) and words[j].endswith(words[i]):
                    count += 1
        return count        

备注：内容来源于stack exchange，提问作者Nyctophilic Enigma