Java嵌套循环代码时间复杂度疑问：为何内层循环最多运行n/2次

首先先明确代码逻辑：你给出的是插入排序的实现框架（仅privateMethod2存在实现bug，不影响时间复杂度推导），外层循环遍历数组第2个到最后一个元素，内层循环向前查找当前元素的插入位置并完成移位。 #

「内层循环最多运行n/2次」的来源澄清 #

你提到的$(n-1)\times \frac{n}{2}$ 实际是最坏场景下所有内层循环的总运行次数，而非单次内层循环的最大运行次数，你是把总次数的平均结果和单次最大值搞混了：

• 最坏场景（数组完全逆序）：每次外层循环调用privateMethod2时，当前元素比前面所有已排序元素都小，内层循环需要跑满当前index次（外层循环的index取值范围是1到n-1），总运行次数就是等差序列求和：$1+2+3+...+(n-1) = \frac{n(n-1)}{2}$
• 把总次数除以共$n-1$次的内层调用，得到平均每次内层循环运行$\frac{n}{2}$次，这就是你得到「最多运行n/2次」结论的来源，但这个表述不准确：
  • 单次内层循环的最大运行次数是$n-1$次（对应外层循环index = n-1且数组完全逆序的场景）
  • $\frac{n}{2}$是平均单次内层循环的运行次数，不是单次最大值

补充：privateMethod2的实现错误说明 #

你当前给出的privateMethod2逻辑有问题，无法完成插入排序的功能：

for (index = end; (index >= begin) && (entry < array[index]); index--){
    array[index + 1] = array[index];
    array[index + 1] = entry;
}

循环体内先将array[index]赋值给index+1位置，又立刻用entry覆盖了这个位置的值，前面的移位操作完全无效，实际运行时这段代码不会改变原数组顺序。正确的插入排序内层逻辑应该把entry的赋值移到循环外：

for (index = end; (index >= begin) && (entry < array[index]); index--){
    array[index + 1] = array[index];
}
array[index + 1] = entry;

最终结论 #

你最初判断的时间复杂度$O(n^2)$是正确的，所谓「内层循环最多运行n/2次」是混淆了平均单次运行次数和单次最大运行次数的结果。

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