调用n次优化版BubbleSort的MultSort函数最坏时间复杂度是多少？

假设BubbleSort()是最优化版本的冒泡排序算法，求该函数的最坏情况时间复杂度？

def MultSort(a,n):
    for i in range(n):
        BubbleSort(a)

选项：

• Linear（线性）
• Quadratic（二次）
• Cubic（三次）

核心分析步骤 #

• 优化版冒泡排序的复杂度：优化版冒泡排序通过标志位判断是否提前终止，最好情况（数组已完全有序）为O(m)（m为数组长度），但最坏情况（数组完全逆序）仍为O(m²)——此时每一轮都要执行完整的比较和交换，无法提前退出。
• MultSort的执行逻辑：
  1. 第一次调用BubbleSort时，若数组处于最坏的逆序状态，耗时为O(m²)。
  2. 第一次排序完成后数组已完全有序，后续n-1次调用BubbleSort时，优化版算法仅需一轮遍历（无交换发生）就会终止，每次耗时O(m)。
• 总复杂度计算：总耗时为O(m²) + (n-1)O(m)。通常此类题目中，函数参数n与数组长度m为同阶变量（即m=n），代入后总复杂度为O(n² + nn) = O(n²)，对应选项中的Quadratic（二次）。

注：如果强行假设每次调用BubbleSort前数组都被重置为逆序（不符合给定代码逻辑），总复杂度会达到O(n³)，但这不是该函数实际执行的最坏情况。

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