如何找到递归选择排序的时间复杂度？

Question

嘿伙计们，我明天有一个测验，我遇到了一些问题，寻找选择排序的递归程序的时间复杂度，任何人都可以解释它是如何 n^2 的。还有一个问题，一些排序算法循环的时间复杂度为 n/2，对于新手问题，/2 是什么意思。

#include <iostream>
using namespace std;

// recursive function to perform selection sort on subarray arr[i..n-1]
void selectionSort(int arr[], int i, int n)
{
    // find the minimum element in the unsorted subarray[i..n-1]
    // and swap it with arr[i]
    int min = i;
    for (int j = i + 1; j < n; j++)
    {
        // if arr[j] element is less, then it is the new minimum
        if (arr[j] < arr[min])
            min = j;    // update index of min element
    }

    // swap the minimum element in subarray[i..n-1] with arr[i]
    swap(arr[min], arr[i]);

    if (i + 1 < n)
        selectionSort(arr, i + 1, n);
}

Answer 1

查找时间复杂度的描述方式通常并不是很有帮助。这是选择排序的工作原理。

通过
算法的第一次，您必须扫描数据的所有n 个元素。

下一次（在递归时），您必须扫描除一个之外的所有内容，即 ( n -1)。

等等。我们可以将查看/比较元素的次数写为：

n + (n-1) + (n-2) + ... + 2 + 1

（你可以对最后一个术语提出质疑，但为了简单起见，我们不会在意。你马上就会明白为什么。）

数学恒等式
这个特定的系列（注意所有的加法）被称为“等差数列”。每项之间的差值是 1。第一项是n，最后一项是 1（​​或 2，无论如何）。

使用一些大多数人在高中不记得（或没有教过）的数学，我们可以将总和重写为：

n(n+1)
??????
  2

（是的，同样，最后一个学期实际上应该是两个，即使我把它留在了一个。）

随着n增长到任意大，
Big O 不太关心n 的友好值。它关心当n变得任意大时会发生什么。我们说“ n向无穷大增长”。

这样做时，我们可以注意到发生了两件事：

• 除以 2 变得微不足道： ?/2 ? ?
• 1（或其他）的加法也无关紧要： ?(?+1) ? ?(?)

所以最终，我们有无穷大，呃，n乘以它自己。该等式简化为：

n(n+1)
??????  ?  n²
  2

复杂度界限
最坏情况下的行为是 n²，因此我们将其注释为“O(n²)”。但请注意，最好的情况也是 n²。我们将其注释为“?(n²)”。最后，由于最好和最坏情况下的行为是相同的，我们对函数的行为有一个非常好的严格限制。我们将其注释为“?(n²)”。

因此，选择排序具有 ?(n²) 复杂度。

神圣的测验！我应该自己做这个！？
是的，不幸的是，弄清楚复杂性是人们认为它真的很容易的事情之一——即使他们自己并不了解它。这需要对数学有一定的了解和一些练习。典型的反应如上面提供的链接所示：“查看这些常见情况并选择最匹配的情况”。我个人认为这不太令人满意。这也是大学教授希望你马上学会的事情之一。

我的建议是：不要太担心。尽最大努力了解基本原理。我们正在做的是找到一个函数（如 y=x²），当它的输入非常大（n ? ?）时，该函数表示算法的行为。

能够跟踪算法所采用的路径并识别这些路径何时是昂贵的，这是比能够提出数学家的答案更重要的能力。如果你真的需要它，你总能找到一位数学家来帮助你，无论是在大学里，还是在互联网上，如果你在正确的地方提问。

而且，当然，请随意花时间尝试更好地理解和练习。能够把事情做对是一项宝贵的技能，不管别人是否看到。

:O)