求冒泡排序代码的时间复杂度精确分析方法

首先纠正一个小误解：你的代码中外层循环是i ← 1 to n-1，所以外层循环总共执行n-1次，不是n次，这是后续分析的基础。

接下来我们分步骤拆解复杂度，同时区分循环迭代、条件判断、交换操作的不同情况：

1. 固定循环迭代次数（与输入无关） #

不管输入数组的有序性如何，外层和内层的循环迭代次数是固定的：

• 外层循环：执行n-1次，对应初始化i、判断i ≤ n-1、递增i这些固定操作，总耗时为常数系数乘以(n-1)。
• 内层循环：对于每个i，j从n downto i+1，迭代次数为n - i次。对i从1到n-1求和，总迭代次数是：

  (n-1) + (n-2) + ... + 1 = n(n-1)/2
  

  这部分对应初始化j、判断j ≥ i+1、递减j的固定操作，总耗时为常数系数乘以n(n-1)/2。

2. 条件判断与交换操作（依赖输入数组） #

这部分的耗时取决于数组中的逆序对数量（即需要交换的相邻元素对数量），我们分三种典型情况分析：

最坏情况（数组完全逆序） #

此时每一次内层循环的if A[j-1] > A[j]判断都为真，每次都要执行交换操作：

• 条件判断执行n(n-1)/2次，耗时为常数系数乘以该次数。
• 交换操作（3次赋值）同样执行n(n-1)/2次，耗时为常数系数乘以该次数。
  把所有操作的耗时加总后，总时间函数是一个二次多项式，最高次项为O(n²)，精确渐进复杂度为Θ(n²)。

最好情况（数组已经完全有序） #

此时每一次条件判断都为假，交换操作一次都不执行：

• 条件判断仍然执行n(n-1)/2次（因为你的代码没有加入“无交换则提前终止”的优化）。
• 交换操作耗时为0。
  总时间函数的最高次项依然是O(n²)——注意：如果加入了提前终止的标志位，最好情况复杂度会降到O(n)，但你的当前代码不包含这个优化。

平均情况 #

假设所有数组排列的概率均等，平均逆序对数量为n(n-1)/4，因此：

• 条件判断还是执行n(n-1)/2次。
• 交换操作平均执行n(n-1)/4次。
  总时间函数的最高次项依然是二次项，平均渐进复杂度为Θ(n²)。

总结 #

• 你关于“内层循环次数需要对i求和”的想法是完全正确的，总和为n(n-1)/2。
• 循环迭代和条件判断的基础次数是固定的，而交换操作的次数完全依赖输入数组的有序性，但无论哪种情况，冒泡排序的渐进时间复杂度都是O(n²)，精确分析下最坏、平均情况为Θ(n²)，未优化的最好情况也为O(n²)。

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