时间戳

首页 > 解决方案 > 排序统计算法已采取的元素数量

algorithm - 排序统计算法已采取的元素数量

问题描述

我从书中阅读了订单统计信息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 行。为什么我们认为 |S|<50？如果 |S| > 50 这个算法有效吗？

在第 4 行，我们为什么要划分 |S|/5？如果我们划分 |S|/4 或 |S|/6 会怎样？

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

标签： algorithmprocedurepseudocode

解决方案

长版：我建议您阅读算法简介（Cormen），第 3 版，第 9.3 节，其中他们解释了最坏情况线性时间的完整细节选择（您可以在那里找到数学）。

简短版：关于为什么选择 |S| < 50 可以看作是一个任意数字。根据步骤 4 中的拆分大小（当前大小为5 ，但可以是4、6如您所说的或任何其他固定正数，它将显示为大 O 计算的常数 T(n) <= T(n/5) + T(7n/10 + 6) + O(n) [来自算法简介]）。

推荐阅读