为什么选择排序最佳情况表示法（Omega 表示法）是 n^2 而不仅仅是 n？

Question

我正在在线学习 CS50，第三周我们学习了算法。 当我们谈到算法的复杂性时，讲座上说选择排序的最坏情况是n^2，因为算法会循环遍历数组，并且每次都会寻找最小的元素，所以

Looping Through an Array (O(n)) * Linear Search in the Array (O(n)) = O(n*n) = O(n^2)

之后，讲师说在最好的情况下（已经排序的数组）我们也会有相同的过程。 但是，之前他说线性搜索的最佳情况（元素在数组中第一个）是Ω(1)，所以我认为选择排序的最佳情况是

Looping Through an Array (Ω(n)) * Linear Search in the Array (Ω(1)) = Ω(n*1) = Ω(n)

我为什么错了？

Answer 1

感谢评论者，我知道我的错误是什么了。 我认为选择排序由

Linear Search for Specific Element

组成，如果元素是第一个，则最好的情况是 Ω(1)，但实际上，它由

Linear Search for the Smallest Element

组成，最好的情况是 Ω(n)，因为即使最小的元素是第一个，算法将不得不循环整个数组，所以：

Looping Through an Array (Ω(n)) * Linear Search for the Smallest Element in the Array (Ω(n)) = Ω(n*n) = Ω(n^2)

感谢各位的评论，你们对我帮助很大。

Answer 2

与此主题相关，我不完全理解为什么我们不能像在冒泡搜索算法中那样从选择排序算法中的循环中“提前退出”。由于“提前退出”的改进，冒泡排序的 omega 为 n，而选择排序的 omega 为 n 平方。