求解冒泡排序执行时间上下限函数及Python可视化实现方法

一、上下限函数推导 #

最优情况（时间下限） #

对应数组已经完全升序的场景：

• 初始change = True触发第一次while循环，进入后先将change赋值为False
• for循环完整执行n-1次，每次仅执行元素比较操作，不会触发元素交换和change重新赋值
• for循环结束后change仍为False，直接退出while循环
• 总操作数为固定常数 + k*(n-1)（k为单次比较的操作系数），属于线性量级，因此时间下限为Ω(n)，精确表达式可写为 T_min(n) = a*n + b，a、b均为与硬件、语言相关的常数，和你猜测的最优时间复杂度结论一致。

最坏情况（时间上限） #

对应数组完全逆序的场景：

• 每轮while循环只能将当前未排序段的最大元素移动到末尾，因此while循环需要执行n-1次
• 每轮for循环的执行次数逐轮递减：第1轮n-1次，第2轮n-2次，最后1轮1次，总for循环迭代次数为n(n-1)/2次
• 每次for循环都会触发if分支的元素交换、change赋值操作，你之前统计的每次迭代4步操作全部会执行
• 总操作数为固定常数 + kn(n-1)/2（k为单次迭代的操作系数），属于二次量级，因此时间上限为O(n²)*，精确表达式可写为 T_max(n) = c*n² + d*n + e，c、d、e均为常数，忽略低阶项和常数后就是你推导的n²量级，你猜测的上限量级是正确的。

二、Matplotlib可视化实现 #

以下是可直接运行的绘图代码，你可以根据实际测试的操作系数调整函数的常数项：

import matplotlib.pyplot as plt
import numpy as np

# 定义上下限模拟函数，系数按照单次操作平均耗时赋值
def lower_bound(n):
    # 最优场景线性函数
    return 1.5 * n + 2

def upper_bound(n):
    # 最坏场景二次函数
    return 2 * n **2 + 2 * n + 1

# 生成数组长度范围
n_list = np.arange(1, 20, 1)
y_lower = lower_bound(n_list)
y_upper = upper_bound(n_list)

# 绘制图像
plt.figure(figsize=(9, 5))
plt.plot(n_list, y_lower, c='g', label='时间下限 Ω(n)')
plt.plot(n_list, y_upper, c='r', label='时间上限 O(n²)')
plt.xlabel('输入数组长度 n')
plt.ylabel('模拟执行操作数')
plt.title('冒泡排序执行时间上下限对比')
plt.legend()
plt.grid(alpha=0.3)
plt.show()

如果需要验证实际运行时间，你可以分别生成完全升序、完全逆序的不同长度数组，用time模块计时打点后叠加到图上，实际打点会完全落在两个函数界定的区间内。

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