逐步寻找选择排序大 theta 符号的过程

Question

我无法确定为此选择排序样本查找大 theta 符号的过程。我在网上读过那个和 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，等等

算法的 "hard part" 正在计算最后 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²).

逐步寻找选择排序大 theta 符号的过程

step by step process of finding selection sort big theta notation

c++

sorting

time-complexity

big-theta

selection-sort