c - 写下这个给定代码的最坏情况运行时间 O(n)？

Question

我得到了以下代码：

void sort(int a[], int n)
{
    for(int i = 0; i < n - 1; i++)
        for(int j = 0; j < n - i - 1; j++)
            if(a[j] > a[j+1])
                swap(a + j, a + j + 1);
}

我必须计算这段代码的最坏情况运行时间 O(n)。

n 是 20，所以我在想，是 O(n) = 20 - 1，还是 O(n)= n-1？

标签： c

Answer 1

任何时候你看到一个双重嵌套的 for 循环，你的第一反应应该是 :likely O(N²)。

但让我们证明一下。

从外循环开始。它将迭代n-1多次。随着n变得非常大，该-1部分可以忽略不计。所以外部循环的迭代非常接近n迭代。

当 时i==0，内部循环将迭代 n-2 次。n但同样，在规模上和规模上并没有太大区别n-2。所以让我们说它迭代n次数。

当 时i==n-2，内部循环将只迭代一次。

因此，内部循环平均迭代n/2次数。

因此，if(a[j] > a[j+1])被评估大约n * n/2次。或n²/2次。对于 Big-O 表示法，我们只关心最大的多项式，而不关心它前面的任何因子。因此，O(N²)是运行时间。最好的、最差的和平均的。