使用频率计数法求解给定算法的时间复杂度并校验推导是否正确

推导错误修正 #

你的原始推导存在三处核心错误：

• 外层循环执行次数计算错误：循环变量i从n-1递减到1（终止条件为i>0），总共执行n-1次，而非n次
• 内层循环总次数的求和变量混淆：你错误将外层循环变量i作为求和的最大值，正确的总执行次数为外层每次循环对应内层次数的累加：(n-1) + (n-2) + ... + 1 = n(n-1)/2，量级为O(n²)
• if条件校验次数计算错误：内层每执行一次循环就会触发一次if判断，因此if的总校验次数和内层循环总次数完全相等，即n(n-1)/2，你推导的(i-1)*i/2少算了接近一倍，逻辑不成立。

if内部语句计数逻辑 #

时间复杂度分三类场景计算：

• 最坏情况：每次if判断arr[i] < arr[i+1]都成立，每次内层循环都会执行内部3条赋值语句，总执行次数为3*n(n-1)/2，量级仍为O(n²)
• 最好情况：if判断永远不成立，内部语句执行次数为0，但外层、内层循环和if判断仍会完整执行，总操作数量级依然是O(n²)
• 平均情况：假设数组元素随机排列，if判断成立的概率为1/2，内部语句总执行次数为3*n(n-1)/4，量级仍然是O(n²)

最终结论 #

无论哪种场景，该算法的时间复杂度均为O(n²)。
注：你提供的代码未使用内层循环变量j，本身逻辑存在冗余，和标准冒泡排序逻辑不符，但不影响时间复杂度的量级计算结果。

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