algorithm - 中位数选择算法

Question

我试图了解寻找中位数的选择算法。我在下面粘贴了伪代码。

SELECT(A[1 .. n], k):
if n<=25
use brute force
else
m = ceiling(n/5)
for i=1 to m
B[i]=SELECT(A[5i-4 .. 5i], 3)
mom=SELECT(B[1 ..m], floor(m/2))
r = PARTITION(A[1 .. n],mom)
if k < r
return SELECT(A[1 .. r-1], k)
else if k > r
return SELECT(A[r +1 .. n], k-r)
else
return mom

我有一个非常微不足道的疑问。我想知道作者上面为 i<=25 写的蛮力是什么意思。是不是他会把元素一个一个的和其他元素一个个比较，看是不是第k大的还是别的。

Answer 1

代码必须来自here .

蛮力算法可以是任何简单而愚蠢的算法。在您的示例中，您可以对 25 个元素进行排序并找到中间的一个。与选择算法相比，这是简单而愚蠢的，因为排序需要 O(nlgn) 而选择只需要线性时间。

当 n 较小时，蛮力算法通常就足够了。此外，它更容易实现。阅读更多关于暴力破解的信息 here .