寻找选择排序大θ表示法的逐步过程

Question

我无法弄清楚为该选择排序示例找到大θ表示法的过程。我在网上读到过，tl;dr 的嵌套循环意味着它将 = O(n^2) 但是，我不知道他们是如何得到它的。我需要逐步找到符号的过程，即添加运营成本和所有内容。如果有人为这个示例代码做到了就好了，这样我就可以更清楚地理解它。预先感谢...

void select(int selct[])
{
    int key;
    int comp;
    for (int i = 0; i < 5; i++)
    {
        key = i;
        for (int j = i + 1; j < 5; j++)
        {
            if (selct[key] > selct[j])
            {
                key = j;
            }
        }
        comp = selct[i];
        selct[i] = selct[key];
        selct[key] = comp;
    }
};

Answer 1

在分析算法的时间复杂度时，我实际上发现不查看代码而是思考驱动算法的核心思想是有帮助的。如果您从概念上知道算法在做什么，那么只需思考算法将要做什么，然后从中推导出时间复杂度，通常会更容易计算出时间复杂度。

让我们在这里应用这种方法。那么选择排序到底是如何工作的呢？嗯，首先找到最后 n 个元素中的最小值并将其交换到位置 0，然后找到最后 n - 1 个元素中的最小值并将其交换到位置 1，然后找到最后 n 中的最小值- 2 个元素并将其交换到位置 2，等等

该算法的“困难部分”是找出最后 n - k 个元素中哪一个最小。选择排序通过迭代这些元素并将每个元素与当前已知的最小元素进行比较来实现这一点。这需要 n - k - 1 次比较。

让我们看看有多少比较。在第一次迭代中，我们需要进行 n - 1 次比较。在第二次迭代中，我们进行 n-2 次比较。第三，我们进行 n-3 次比较。总结比较次数为我们提供了衡量总工作量的好方法：

(n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1 = n(n - 1) / 2

这是一个著名的总结——值得牢记在心——它告诉我们需要进行多少次比较。进行比较的次数可以很好地代表已完成的工作总量。由于进行了 n(n - 1) / 2 = n² / 2 - n / 2 = θ(n²) 次比较，因此选择排序的时间复杂度为 θ(n²)。