顺序统计算法已采取的元素进行处理的数目

Question

我从The Design and Analysis of Computer Algorithms", by Aho, Hopcroft, Ullman, Addison-Wesley这本书中读取了订单统计数据

算法3.6。查找第k个最小元素

步骤如下:

procedure SELECT(k, S):
1.  if |S| < 50 then

begin
2.          sort S:
3.          return kth smallest element in S

end
else

begin
4.          divide S into L|S|/5 J sequences of 5 elements each  *lower bound*
5.          with up to four leftover elements:
6.          sort each 5-element sequence;
7.          let M be the sequence of medians of the 5-element sets;
8.          m <- SELECT(||M|/2|, M);      *Upper bound*
9.          let S1, S2 , and S3 be the sequences of elements in S less
than, equal to, and greater than' m, respectively;
10.         if |S_1|>= k then return SELECT(k_1, S_1)
else ,
11.         if (|S_1| + |S_2| >= k) then return m
12.         else return SELECT(k- |S_1| - |S_2|, S_3)
end

第1行。为什么我们要考虑50美元?If |S|>这个算法是50个工作的呢?

在第4行，为什么我们划分|S|/5?如果我们除以|S|/4或|S|/6呢?

如果有人能澄清我的疑问，那将是很大的帮助。谢谢你。

Answer 1

长版:我建议你阅读Introduction to Algorithms(Cormen)， 3rd edition, Section 9.3，在那里他们详细解释了在最坏情况下的线性时间选择(你可以在那里找到数学)。

短版:关于为什么要选|S| <50可以看作是一个任意的数字。选择这种方式是为了满足函数的大O计算(如n₀)，根据步骤4的分割大小(当前大小为5，但可以是4,6，如您所述或任何其他固定的正数，它将在大O计算中显示为常数T(n) <= T(n/5) + T(7n/10 + 6) + O(n)[来自算法介绍])。