为什么选择排序的复杂度不是阶乘？
Why isn’t the complexity of selection sort n factorial?
如果选择排序在数组上迭代n次，n是数组的长度，每次迭代比上一次少1次比较（第一次迭代有n次比较），选择排序的复杂度如何是 n^2 而不是 n!(n 阶乘)?
通常，当您多次执行某些操作时，会出现运行时间的倍增。因此，例如，如果我进行 10 次操作 5 次，那么我将总共进行 50 次操作。
另一方面，当你做一件事，然后做下一件事时，运行时间会增加。所以，例如，如果我做 10 个工作单元，那么我会做 5 个工作单元共15个作业单元。
你是正确的，选择排序首先查看 n 个项目，然后是 n-1 个项目，然后是 n-2 个项目，然后是 n-3 个项目，等等。问题是我们如何从中得出一个总数运行。您提议将它们相乘：
n · (n-1) · (n-2) · ... · 2 · 1
然而，这意味着“我做 n 次事情 n-1 次，然后做 n-2 次，然后做 n-3 次，等等”
这就是我们将它们加在一起的原因：
n + (n-1) + (n-2) + ... + 2 + 1 = n(n+1)/2 = Θ(n2).
如果选择排序在数组上迭代n次，n是数组的长度，每次迭代比上一次少1次比较（第一次迭代有n次比较），选择排序的复杂度如何是 n^2 而不是 n!(n 阶乘)?
通常，当您多次执行某些操作时，会出现运行时间的倍增。因此，例如，如果我进行 10 次操作 5 次，那么我将总共进行 50 次操作。
另一方面，当你做一件事，然后做下一件事时，运行时间会增加。所以，例如，如果我做 10 个工作单元，那么我会做 5 个工作单元共15个作业单元。
你是正确的，选择排序首先查看 n 个项目，然后是 n-1 个项目，然后是 n-2 个项目，然后是 n-3 个项目，等等。问题是我们如何从中得出一个总数运行。您提议将它们相乘：
n · (n-1) · (n-2) · ... · 2 · 1
然而，这意味着“我做 n 次事情 n-1 次，然后做 n-2 次，然后做 n-3 次，等等”
这就是我们将它们加在一起的原因：
n + (n-1) + (n-2) + ... + 2 + 1 = n(n+1)/2 = Θ(n2).