我相信有一种方法可以找到长度为n的O(n)无序数组中第k大的元素。也可能是期望O(n)之类的。我们该怎么做呢?
当前回答
还有Wirth的选择算法,它的实现比QuickSelect简单。Wirth的选择算法比QuickSelect慢,但经过一些改进,它变得更快。
更详细地说。使用Vladimir Zabrodsky的MODIFIND优化和3中位数的枢轴选择,并注意算法划分部分的最后步骤,我提出了以下算法(想象一下,命名为“LefSelect”):
#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }
# Note: The code needs more than 2 elements to work
float lefselect(float a[], const int n, const int k) {
int l=0, m = n-1, i=l, j=m;
float x;
while (l<m) {
if( a[k] < a[i] ) F_SWAP(a[i],a[k]);
if( a[j] < a[i] ) F_SWAP(a[i],a[j]);
if( a[j] < a[k] ) F_SWAP(a[k],a[j]);
x=a[k];
while (j>k & i<k) {
do i++; while (a[i]<x);
do j--; while (a[j]>x);
F_SWAP(a[i],a[j]);
}
i++; j--;
if (j<k) {
while (a[i]<x) i++;
l=i; j=m;
}
if (k<i) {
while (x<a[j]) j--;
m=j; i=l;
}
}
return a[k];
}
在我这里做的基准测试中,LefSelect比QuickSelect快20-30%。
其他回答
下面是完整实现的链接,其中相当广泛地解释了在无序算法中查找第k个元素的算法是如何工作的。基本思想是像快速排序一样对数组进行分区。但为了避免极端情况(例如每一步都选择最小的元素作为主元,使算法运行时间退化为O(n^2)),采用特殊的主元选择,称为中位数的中位数算法。在最坏情况和平均情况下,整个解在O(n)时间内运行。
这里是全文的链接(它是关于寻找第k个最小的元素,但寻找第k个最大的元素的原理是相同的):
在无序数组中寻找第k个最小元素
我实现了在n个未排序元素中寻找第k个最小值的动态规划,特别是竞赛方法。执行时间为O(n + klog(n))。所使用的机制在维基百科关于选择算法的页面上被列为方法之一(如上面的帖子之一所示)。你可以阅读算法,也可以在我的博客页面“查找k个最小值”上找到代码(java)。此外,逻辑可以对列表进行部分排序——在O(klog(n))时间内返回第一个K min(或max)。
虽然代码提供了第k个最小值的结果,但可以使用类似的逻辑来查找O(klog(n))中的第k个最大值,忽略创建比赛树的前期工作。
如果你想要一个真正的O(n)算法,而不是O(kn)或类似的算法,那么你应该使用快速选择(它基本上是快速排序,你会丢弃你不感兴趣的分区)。我的教授写了一篇很棒的文章,包括运行时分析:(参考)
QuickSelect算法可以快速找到包含n个元素的无序数组中的第k个最小元素。这是一个随机算法,所以我们计算最坏情况下的预期运行时间。
这是算法。
QuickSelect(A, k)
let r be chosen uniformly at random in the range 1 to length(A)
let pivot = A[r]
let A1, A2 be new arrays
# split into a pile A1 of small elements and A2 of big elements
for i = 1 to n
if A[i] < pivot then
append A[i] to A1
else if A[i] > pivot then
append A[i] to A2
else
# do nothing
end for
if k <= length(A1):
# it's in the pile of small elements
return QuickSelect(A1, k)
else if k > length(A) - length(A2)
# it's in the pile of big elements
return QuickSelect(A2, k - (length(A) - length(A2))
else
# it's equal to the pivot
return pivot
这个算法的运行时间是多少?如果对手为我们抛硬币,我们可能会发现主元总是最大的元素,k总是1,给出的运行时间为
T(n) = Theta(n) + T(n-1) = Theta(n2)
但如果选择确实是随机的,则预期运行时间由
T(n) <= Theta(n) + (1/n) ∑i=1 to nT(max(i, n-i-1))
我们做了一个不完全合理的假设递归总是落在A1或A2中较大的那个。
让我们猜测对于某个a T(n) <= an,然后我们得到
T(n)
<= cn + (1/n) ∑i=1 to nT(max(i-1, n-i))
= cn + (1/n) ∑i=1 to floor(n/2) T(n-i) + (1/n) ∑i=floor(n/2)+1 to n T(i)
<= cn + 2 (1/n) ∑i=floor(n/2) to n T(i)
<= cn + 2 (1/n) ∑i=floor(n/2) to n ai
现在我们要用加号右边这个可怕的和来吸收左边的cn。如果我们将其限定为2(1/n)∑i=n/2到n an,我们大致得到2(1/n)(n/2)an = an。但是这个太大了,没有多余的空间来挤进一个cn。让我们用等差级数公式展开和:
∑i=floor(n/2) to n i
= ∑i=1 to n i - ∑i=1 to floor(n/2) i
= n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2
<= n2/2 - (n/4)2/2
= (15/32)n2
我们利用n“足够大”的优势,用更干净(更小)的n/4替换丑陋的地板(n/2)因子。现在我们可以继续
cn + 2 (1/n) ∑i=floor(n/2) to n ai,
<= cn + (2a/n) (15/32) n2
= n (c + (15/16)a)
<= an
提供了> 16c。
得到T(n) = O(n)显然是(n)所以我们得到T(n) = (n)
你确实喜欢快速排序。随机选择一个元素,然后将所有元素推高或推低。此时,您将知道您实际选择了哪个元素,如果它是第k个元素,您就完成了,否则您将重复bin(更高或更低),第k个元素将落在其中。从统计学上讲,找到第k个元素所需的时间随着n, O(n)而增加。
这叫做求k阶统计量。有一个非常简单的随机算法(叫做quickselect),平均时间为O(n),最坏情况时间为O(n²),还有一个相当复杂的非随机算法(叫做introselect),最坏情况时间为O(n)。维基百科上有一些信息,但不是很好。
你需要的一切都在这些幻灯片里。只需提取O(n)最坏情况算法(introselect)的基本算法:
Select(A,n,i):
Divide input into ⌈n/5⌉ groups of size 5.
/* Partition on median-of-medians */
medians = array of each group’s median.
pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
Left Array L and Right Array G = partition(A, pivot)
/* Find ith element in L, pivot, or G */
k = |L| + 1
If i = k, return pivot
If i < k, return Select(L, k-1, i)
If i > k, return Select(G, n-k, i-k)
在Cormen等人的《算法介绍》一书中也有非常详细的描述。