比较的理论分析

Question

我首先被要求开发一个简单的排序算法，将整数数组按升序排序并将其写入代码：

int i, j;

    for ( i = 0; i < n - 1; i++)
    {
        if(A[i] > A[i+1])
            swap(A, i+1, i);

        for (j = n - 2; j >0 ; j--)
            if(A[j] < A[j-1])
                swap(A, j-1, j);
    }

现在有了排序功能，让我对算法的运行时间做一个理论分析。它说答案是 O(n^2) 但我不太确定如何证明这种复杂性。

到目前为止我所知道的是第一个循环从 0 运行到 n-1，（所以 n-1 次），第二个循环从 n-2 运行到 0，（所以 n-2 次）。

做递归关系：

let C(n) = the number of comparisons
for C(2) = C(n-1) + C(n-2)
         = C(1) + C(0)
    C(2) = 0 comparisons?
    C(n) in general would then be: C(n-1) + C(n-2) comparisons?

如果有人能逐步指导我，将不胜感激。

Answer 1

在进行 "real" 大 O - 时间复杂度分析时，您 select 一个您计算的操作，显然是支配运行时间。在您的情况下，您可以选择比较或交换，因为最坏的情况下会有很多交换对吗？

然后你计算这将被唤起多少次，缩放到输入。所以在你的情况下你的分析是完全正确的，你只需这样做：

C = O((n - 1)(n - 2)) = O(n^2 -3n + 2) = O(n^2)

我通过推理您代码中的数据流得出这些数字。您有一个外部 for 循环迭代对吗？在那个 for 循环中，您有另一个 for 循环迭代。第一个 for 循环迭代 n - 1 次，第二个 for 循环迭代 n - 2 次。由于是嵌套的，所以实际的迭代次数实际上是这两者的乘，因为外层循环的每一次迭代，整个内层循环都在运行，做n - 2次迭代。

您可能知道，在进行时间复杂度分析时，您总是会删除除主导项以外的所有项。

关于最坏情况复杂度和平均情况下限，还有很多要补充的内容，但这有望让您掌握如何推理大 O 时间复杂度分析。

我见过很多用于实际分析表达式的不同技术，例如您的递推关系。然而，我个人更喜欢只对代码进行推理。很少有算法具有难以计算的上限，另一方面，下限通常很难计算。

Answer 2

您的分析是正确的：外循环进行 n-1 次迭代。内循环使得 n-2.

因此，对于外循环的每次迭代，内部循环都有 n-2 次迭代。因此，总步数为 (n-1)(n-2) = n^2-3n+2.

主要术语（在大 O 分析中很重要）是 n^2，所以你得到 O(n^2) 运行时间。

我个人不会在这种情况下使用递归方法。写递归方程通常对递归函数很有帮助，但在像这样更简单的算法中，有时查看代码和做一些简单的数学运算会更容易。

比较的理论分析

theoretical analysis of comparisons

sorting

algorithm

performance