2

我想知道为什么 QuickSelect 应该是一种性能如此出色的算法，可以从 n 大小的未排序集合中找到任意元素。我的意思是，当你一个一个地遍历所有元素时，直到你找到所需的元素，它需要 O(n) 比较——这就是快速选择的最佳情况，而且容易得多。

我错过了一些重要的东西吗？QiuckSelect 是否存在比线性搜索更好的情况？

4

1 回答 1

0

平均中的 QuickSelect 更适合在未排序的数组中找到第 k 个最小（最大）数字（项目）

于 2015-02-04T18:35:26.583 回答