为什么说选择排序的算法复杂度是O(n2) ?

Question

试了下，远不到O(n^2)
下面的例子输出为105次排序，不到255次（15x15）一半？

var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]

var count = 0

var len = arr.length
for (let i = 0; i < len - 1; i++) { // 最后一个不用排
    let minIndex = i
    for (let j = i + 1; j < len; j++) { // 从下一个开始找最小值
        count++
        if (arr[minIndex] > arr[j]) {
            minIndex = j
        }
    }
    const tmp = arr[minIndex]
    arr[minIndex] = arr[i]
    arr[i] = tmp
}

console.log(arr, count)
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] 105

Answer 1

大 O 复杂度人家全称叫时间渐进复杂度，算的是当 n 趋近无穷大时的最高阶项，也就是不包含低阶项和首项常系数，因为当 n 无穷大时，低阶项和常系数对结果就几乎没有影响了（这几个概念名词不明白就说明大一上学期的高数就没听过课）。

实际上在不同情况下有最坏、最好、平均、均摊四种可能的结果。不特殊指明一般就指平均复杂度（大多数情况平均、最好和最坏三者应该相同）。

你这个例子里确实是 105 次循环没错，因为本来实际的值也是这个（ (15 * (15 - 1)) / 2 = 105 ）。

(n * (n - 1)) / 2，去掉常数项和低阶项 -1 和 1/2，复杂度即为 O(n^2)。

还不明白怎么算的，捡起来大一上高数课本吧，这已经跟编程知识无关了，而是数学知识了。