选择排序算法时间复杂度

Question

在选择排序中，外层循环时间复杂度为 0(n)，内层循环时间复杂度为 (n[n-1])/2 那么为什么我们要在外层循环和内层循环中添加时间复杂度：n + (n [n-1])/2 而不是乘法？

由于它是一个嵌套循环，因此它必须是多个。但如果我们乘以时间复杂度将变为 0(n^3) 而不是 0(n^2)

Answer 1

在选择排序中，内循环在第一次迭代中运行

n - 1

次，在第二次迭代中运行

n - 2

次，依此类推，直到在最后一次迭代中运行

1

次。

外循环控制内循环迭代的次数。

前

n - 1

个自然数的和为

n * (n - 1) / 2

，其复杂度为

O(n^2)

。

我鼓励您阅读维基百科上的选择排序文章。