判断含三层嵌套循环算法的时间复杂度：O(m*n)还是O(m*n²)？

泛化伪代码 #

currRow = 0
for line in file:
    for match in re.finditer(r"\d+", line):
        for i in range(match.start(), match.end()):
            print(currRow, i) # placeholder, 实际逻辑不影响复杂度分析
    currRow += 1

问题背景 #

输入为每行长度一致的文本文件，可视为m行n列的网格（m为行数，n为每行字符数）。需要判断该算法的时间复杂度是O(mn)还是O(mn²)。

用户的困惑点在于两个内层循环的关系：单独看每个内层循环都随n增长，但直觉认为二者相关，整体不会出现O(n²)的操作。用户的分析思路为：内层循环遍历所有匹配项，每个匹配的最大长度为n/匹配数，总操作数为匹配数*(n/匹配数)=n，渐近复杂度为O(n)，想验证该分析是否正确。

解答 #

你的分析完全正确，该算法的时间复杂度是O(m*n)，理由如下：

• 最外层循环执行m次，这部分无争议。
• 聚焦单一行的操作：正则匹配出的所有数字子串，其包含的字符总数最多为n（整行都是数字的情况），最少为0。内层的两个循环本质是遍历所有数字字符——每个数字字符只会被处理一次，不会重复迭代。
• 假设一行有k个数字子串，长度分别为l₁、l₂…lₖ，那么两个内层循环的总迭代次数是l₁+l₂+…+lₖ ≤n，因此单一行的时间复杂度为O(n)。
• 整体时间复杂度即为mO(n) = O(mn)，不可能达到O(m*n²)，因为不存在“对每个字符做n次操作”的嵌套逻辑，所有内层操作的总规模严格受限于每行的字符总数n。

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