升序排序代码Big O时间复杂度O(N²)计算正确性核验咨询

你提供的代码如下：

for (int i = 0; i < 4344; i++)
{
    for (int j = i + 1; j < 4344; j++)
    {
        if (array_dist[index_arr[i]] > array_dist[index_arr[j]])
        {
            x = index_arr[i];
            index_arr[i] = index_arr[j];
            index_arr[j] = x;
        }

    }
}

你的推导结论是对的，这段代码的时间复杂度确实是O(N²)，if语句不会改变最终的时间复杂度结果，具体原因如下：

• 这段代码是典型的嵌套循环结构，外层循环执行N次（这里固定N=4344），内层循环每次执行次数为N-i-1次，总循环次数为N*(N-1)/2，本身就是O(N²)的量级，大O表示法会忽略常量系数，所以和N²属于同阶复杂度。
• if判断本身是常量时间O(1)操作，内部的3次赋值也都是常量时间操作：最坏情况下（待排序序列完全逆序）每次if判断都命中，每次内层循环的总操作数是1次判断+3次赋值，依然是O(1)量级；最好情况下（待排序序列完全升序）if判断都不命中，每次内层循环只执行1次判断，还是O(1)量级。
• 你之前的计算逻辑里有个小误差：3次操作不是直接加在N²上，而是每次内层循环最多多3次常量操作，相当于总操作数的常量系数变大，但大O表示法会忽略所有常量系数和低阶项，所以不会改变最终复杂度等级。
• 额外补充：这段代码没有设置提前跳出循环的逻辑，不管待排序序列的初始顺序如何，都必须跑完所有嵌套循环的比较逻辑，所以它的最好、最坏、平均时间复杂度都是O(N²)。

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