关于冒泡排序时间复杂度为O(n²)而非O(n³)的疑问

我的问题背景 #

我刚接触Python和大O表示法，最近练习写冒泡排序的时候，一直在思考它的时间复杂度应该是多少。这是我写的代码：

def bubblesort(num_list, sort_type):
    """Returns the list of numbers in ascending order, descending order"""
    ite = len(num_list) - 1

    if sort_type == "asc":
        for i in range(ite):
            for n in range(ite - i):
                if num_list[n] > num_list[n + 1]:
                    temp = num_list[n + 1]
                    num_list[n + 1] = num_list[n]
                    num_list[n] = temp
    elif sort_type == "desc":
        for i in range(ite):
            for n in range(ite - i):
                if num_list[n] < num_list[n + 1]:
                    temp = num_list[n + 1]
                    num_list[n + 1] = num_list[n]
                    num_list[n] = temp
    else:
        pass
    return num_list

我原本以为，外层循环、内层循环和条件判断都会随着输入规模线性增长，所以时间复杂度应该是O(nnn)=O(n³)，但查资料发现它其实是O(n²)，我搞不懂为什么不是立方级的。

解答 #

嘿，我来帮你理清这个误区～

你这里的关键误解是把条件判断的时间复杂度当成了O(n)，但实际上它是O(1)（常数时间），这才是问题的核心：

• 外层循环：总共执行n-1次（n是列表长度），大O记法里忽略常数，所以是O(n)
• 内层循环：每次外层循环结束后，内层循环的执行次数会递减——第一次跑n-1次，第二次n-2次，直到最后一次跑1次。把这些次数加起来是：(n-1)+(n-2)+...+1 = n(n-1)/2，这个结果的量级是n²，所以内层循环整体是O(n²)
• 至于条件判断和交换操作：不管你的列表有多大，比较两个元素的大小、做三次赋值交换，都是固定的几步操作，不会随n的增长而变多，所以每一次执行都是O(1)

把这些结合起来看，总时间复杂度就是「外层循环次数 × 内层循环次数 × 每次内层循环操作的时间」，也就是O(n × n × 1) = O(n²)，完全到不了O(n³)的量级。

举个具体的例子：如果n是100，外层循环跑99次，内层循环的总次数大概是(99×100)/2=4950次，整个算法的总操作次数就是几千级，是n²的规模；如果是O(n³)的话，总操作次数会是百万级，这和冒泡排序的实际运行情况完全不符。

另外提一句，你的代码里asc和desc的逻辑几乎一样，可以把内层循环的逻辑抽成一个辅助函数，这样代码会更简洁，但这对时间复杂度没有影响哦～

备注：内容来源于stack exchange，提问作者Zija Igidov