c - 不确定我的 Big O 分析

Question

int RiskSort(int* PlayerA, int* PlayerB,int Length){
    int i,j;
    int Losses = 0;
    for(i=0;i<Length-Losses;i++){
         printf("%d,%d\n",PlayerA[i],PlayerB[i]);
        if(PlayerB[i]<PlayerA[i]){
                for(j=i;j<((Length-1)-Losses);j++){
                    Swap(&PlayerB[j],&PlayerB[j+1]);
                }
                i--;
                Losses++;
        }

    }
return Losses;

}

我刚刚写了这个，我得到 O(n log n) 作为我的答案，这是家庭作业，但 Big O 部分只是我的学习方式。

再次感谢

编辑:我从第一个 for 循环中得到 N，在 if 上得到 N-1-X 次传递，我不确定如何标记它，因为它限制了传递量，我称之为 log n(可能是不准确，但我找不到不查看代码并在线选择的指南)

编辑 2:只是试图让这个函数更有效率

int RiskSortB(int* PlayerA, int* PlayerB,int Length){
int i,j;
int Losses = 0;
for(i=0;i<Length-Losses;i++){
j=i+1;
if(PlayerB[i]<PlayerA[i])
    Losses++;

while(PlayerB[i]<PlayerA[i]&&j<Length){
    if(PlayerB[j]>=PlayerA[i]){
        Swap(&PlayerB[i],&PlayerB[j]);
        if(j!=(Length-Losses))
            Swap(&PlayerB[j],&PlayerB[Length-Losses]);
    }
    j++;
}


}

return Losses;
}

因此，由于每个 for 循环调用最大 Swap 的时间量是 2，这意味着它的 O(2N) 但常数无关紧要，所以它的 O(N) 对吗？

Answer 1

假设 PlayerB 的每个元素都导致“损失”。对于第一个元素，您执行 Length-1 交换。对于第二个元素，您执行 Length-2 交换。对于第三个元素，您执行 Length-3 交换。等等

总共有多少交换？多达 1 + 2 + ... + (n-1)。当您看到这个整数序列时，请应用高斯公式:整数之和 1..n = n * (n + 1)/2 = (n² + n)/2。即O(n²).

(sum(1..n) 和 sum(1..(n-1)) 之间的区别不影响 big-O。)