c - 时间 计算复杂度？

Question

我下面有这个排序代码，它是冒泡排序，但我认为这个代码不完全是 O(N^2) 。我想知道下面这段代码的时间计算复杂度(用大 O 表示)是多少。我猜是 O(N.logN)。

这里给出的代码只是作为示例，并不声称它是可编译的。

for(i = 0; i < n-1; i++)
{
    for(j = 0; j < n-i-1; j++)
    {
        if (a[j+1] < a[j])
        {
            temp = a[j];
            a[j] = a[j+1];
            a[j+1] = temp;
        }
    }
}

Answer 1

My guess it is O(N.logN).

为什么要猜测？看看实际发生了什么......

第一次通过外循环时，i == 0。这意味着 j 的范围从 0 到 n-1。

第二次时，i == 1，因此 j 的范围为 0 到 n-2。

第三次，i == 2，所以 j 的范围从 0 到 n-3。

...

最后一次，i == n-1，因此 j 的范围从 0 到 0。

因此，操作总数为 n-1 + n-2 + n-3 + ... + 0。

总和 Σi, i=0..n-1 是多少？现在将其转换为大 O 界限。