450 BLUM ET AL.
PICK operates by successively discarding (that is, removing from S) subsets of S
whose elements are known to be too large or too small to be i 0, until only i 0 remains.
Each subset discarded will contain at least one-quarter of the remaining elements.
PICK is quite similar to the algorithm FIND (Hoare [5]), except that the element m
about which to partition S is chosen more carefully.
PICK will be described in terms of three auxiliary functions
b(i, n), c(i, n),
and
d(i, n),
which will be chosen later. We will omit argument lists for these functions
in general, as no confusion can arise. Since we are interested in the asymptotic
properties of PICK, we will also omit details to be given in Sec. 3 regarding the case
when n mod c :A 0.
PICK:
(Selectsi0S, wherelSl =nandl ~i~<n)
1. (Select an element m ~ S):
(a) Arrange S into
n/c
columns of length
c,
and sort each column.
(b) Select m--b 0 T, where T-'aet the set of
n/c
elements which are the
d-th smallest element from each column. Use PICK recursively if
n[c > 1.
2. (Compute m p S): Compare m to every other element x in S for which it is
not yet known whether m < x or m > x.
3. (Discard or halt): If m p S -- i, halt (since m -- i 0 S), otherwise if m p S > i,
discard D --
{xlx ~ m}
and set n ~-- n -- [D [, otherwise discard D =
{xlx <~ m}
and set n +-- n -- I D 1, i ~ i- I D I.
Return to step
1.
This completes the description of PICK. We are now ready to prove:
THEOREM 1.
f (i,
n) -- d)(n).
Proof.
We show that a reasonable choice of functions
b(i, n), c(i, n),
and
d(i, n)
result in a linear time selection algorithm. Let
h(c)
denote the cost of sorting c numbers
using Ford and Johnson's algorithm [2]. It is known [3] that:
h(c) = ~ Ilog~(3j/4)]. (4)
l~<j~c
The cost of step l(a) is
n • h(c)/c,
making obvious the fact that
c(i, n)
must be bounded
above by a constant in order for PICK to run in linear time.
Letting
P(n)
denote the maximum cost of PICK for any i, we can bound the cost
of step l(b) by
P(n/c).
After step 1, the partial order determined for S may be
represented as in Fig. 1.
Here we have the
n/c
columns of length c portrayed with their largest elements on
top. Since the recursive call to PICK in step l(b) determines which elements of T
are <m, and which are >m, we separate the columns as in Fig. 1. Every element
剩余13页未读，继续阅读
Anova.YJ
- 粉丝: 222
- 资源: 6
我的内容管理
展开
最新资源
- C++多态实现机制详解：虚函数与早期绑定
- Java多线程与异常处理详解
- 校园导游系统：无向图实现最短路径探索
- SQL2005彻底删除指南：避免重装失败
- GTD时间管理法：提升效率与组织生活的关键
- Python进制转换全攻略：从10进制到16进制
- 商丘物流业区位优势探究：发展战略与机遇
- C语言实训：简单计算器程序设计
- Oracle SQL命令大全：用户管理、权限操作与查询
- Struts2配置详解与示例
- C#编程规范与最佳实践
- C语言面试常见问题解析
- 超声波测距技术详解：电路与程序设计
- 反激开关电源设计：UC3844与TL431优化稳压
- Cisco路由器配置全攻略
- SQLServer 2005 CTE递归教程：创建员工层级结构
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
