为何三层O(n)操作嵌套的时间复杂度仍为O(n²)？附代码分析

Question : "evaluate the average and the worst-case complexity, using the following notation : n = len(a)."

def anagramme_list(a, b):
    # Time complexity : O(n^2) O(n^2)
    # Space complexity : ~O(n) (list made out of a string)

    res = False  # O(1) O(1)

    if len(a) == len(b):  # (cond O(1)) O(n^2) O(n^2)
        liste_b = list(b)  # O(n) O(n)
        res = True  # O(1) O(1)

        for i in a:  # (it: O(n)) O(n^2) O(n^2)
            if i in liste_b:  # (cond O(n)) O(n) O(n)
                liste_b.remove(i)  # O(n) O(n)
            else:  # O(1) O(1)
                res = False  # O(1) O(1)

    return res

疑问 #

我原本认为该函数最坏时间复杂度为O(n³)，因为外层O(n)的循环中嵌套了O(n)的i in liste_b判断，该判断为真时还会触发O(n)的liste_b.remove(i)操作，三层O(n)操作嵌套应为O(n³)，但给出的答案却是O(n²)。请解释为何这三层O(n)操作的总复杂度不是O(n³)，以及此类场景下Big O复杂度评估的通用方法。

为什么复杂度是O(n²)而非O(n³)？ #

核心原因是**liste_b的元素数量有限，in和remove操作的总执行成本不会达到O(n³)**：

• 外层循环确实执行n次，但每次循环里的i in liste_b和liste_b.remove(i)的时间成本，会随着liste_b的长度递减：初始时liste_b长度为n，每执行一次remove，长度就减1。
• 把所有循环中in和remove的时间加起来：第一次循环成本是n（查找）+n（删除），第二次是(n-1)+(n-1)，……，最后一次是1+1。总时间是2*(n + (n-1) + ... +1) = n(n+1)，这属于O(n²)的量级。
• 哪怕是最坏情况（比如a和b完全相同，每次循环都要执行查找和删除），总操作次数也只是O(n²)，不会是O(n³)——因为不会每次都做完整的n次查找和删除，liste_b的长度在持续缩短，后续操作的成本越来越低。

此类场景的Big O评估通用方法 #

• 别直接按嵌套层数相乘：当内层操作的时间依赖外部状态（比如容器长度变化）时，不能简单把每层的O(n)相乘，要计算所有操作的总累加成本。
• 关注操作的总上限：对于会修改容器长度的操作，统计这类操作的总执行次数上限。比如remove最多执行n次，每次的时间随容器长度递减，累加后是O(n²)而非O(n³)。
• 拆分步骤单独计算：把每个独立操作（循环、查找、删除）的时间分开算，再求和，最后保留最高量级的项即可。

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