algorithm - 找到第 i 个最大的元素

Question

我想使用分而治之的过程来计算一行整数中的第 i 个最大元素，并分析算法的渐近时间复杂度。

Algorithm ith(A,low,high){
   q=partition(A,low,high);
   if (high-i+1==q) return A[q];
   else if (high-i+1<q) ith(A,low,q-1);
   else ith(A,q+1,high);
}

是吗？如果是这样，我们如何找到它的时间复杂度？

时间复杂度由以下递归关系描述:

T(n)=T(n-q)+T(q-1)+Θ(n)

但是我们如何在不知道 q 值的情况下解决这个递推关系呢？

或者是否有一种时间复杂度较低的算法可以计算一行整数中第 i 个最大的元素？

Answer 1

这是 quick select 的变体算法(找到 i-th 最小元素而不是 i-th 最大元素)。它在最坏情况下的运行时间为 O(n^2)，在平均情况下为 O(n)。

要查看最坏的情况，假设您正在搜索 nth 最大的元素，而算法总是选择 q 作为剩余元素中的最大元素范围。所以你将调用 ith<​​ 函数 n 次。此外，分区子例程占用 O(n)，因此总运行时间为 O(n^2)。

要了解平均案例分析，请查看Tim Roughgarden教授的解释here .