该算法的最坏情况渐近成本是多少？

Question

void Ordena(TipoItem *A, int n)
{

    TipoItem x;

    int i, j;

    for (i = 1; i < n; i++)
    {

        for (j = n; j > i; j--)
        {

            if (A[j].chave < A[j - 1].chave)
            {

                x = A[j];

                A[j] = A[j - 1];

                A[j - 1] = x;
            }
        }
    }

}

我认为最坏的情况是数组按降序排列，对吗？关于移动次数方面的渐近成本，是 O(n²) 还是 O(2n²) ？我刚刚开始学习渐近成本（如您所知）。

Answer 1

正如您所说的 worst-case 场景是数组按降序排列的场景，因为您必须每次都执行 if 语句。然而，由于我们正在谈论渐近符号，因此是否执行 if 语句是完全无关紧要的，因为这三个指令的成本实际上是常数（i.d.O(1)）。因此，这里重要的是你实际上必须循环遍历数组中的元素多少次，如果你进行数学计算，这恰好发生了 n^2/2 + n/2 次。因此，计算复杂度为 O(n^2)，因为这里的主要部分是 n^2/2，并且渐近符号没有考虑乘法因子 1/2，即使有时这些因素会影响执行时间.

该算法的最坏情况渐近成本是多少？

What is the worst-case asymptotic cost of this algorithm?

sorting

complexity-theory

big-o