用quickselect求n个排序数组中第k个最大元素的时间复杂度

Question

如果您有J长度N的排序数组，请查找其中Kth最小的元素。这里有一些潜在的解决方案，有些涉及最小堆或二进制搜索，但我想知道使用QuickSelect的时间复杂度是多少。如果我们简单地将每个数组连接在一起，并在组合数组上使用quickselect。

Quickselect在一般情况下以线性时间运行，但是数组的组合确实会扩展搜索空间，但它比使用合并策略更有效，因为如果选择了好的枢轴，Quickselect必然允许忽略某些元素。

Answer 1

Quickselect与quicksort非常相似，因为它的分而治之策略。2之间的不同之处在于，Quickselect将只对包含第k个最小元素的部分数据重复出现，并将一直持续到间隔等于k值，这意味着它已经找到了第k个最小值（https://www.geeksforgeeks.org/Quickselect-algorithment/）。关于你的问题，我认为你说的是对的，这取决于你在重复时得到的枢轴。在最好的情况下，时间仍然需要O(n)（因为Quickselect只搜索拆分数据的1部分，n的大小取决于您的数据集），在最坏的情况下，当选择了错误的枢轴时，时间仍然需要O(n^2)。为了使该算法得到推广，很难为每一组数据找到“最佳可能”的枢轴。

在考虑首先使用堆作为方法时，当给定数据时，首先构建堆需要O(n)个时间。为了找到第k个最小的项，堆中的最小元素，即根，必须被找到k次。移除一个min堆中的min只需要1个团队，但是在移除根之后对堆进行堆化将需要O（logn）时间，根据您所讨论的输入大小，这可能会增加相当大的成本。因此，堆方法的总时间为O(1)+O(klogn)，其中k是第k个最小的数。

基本上，效率的差异实际上取决于在Quickselect中如何选择枢轴，以及考虑堆方法时输入的大小或k值。