毕业论文
计算机论文
经济论文
生物论文
数学论文
物理论文
机械论文
新闻传播论文
音乐舞蹈论文
法学论文
文学论文
材料科学
英语论文
日语论文
化学论文
自动化
管理论文
艺术论文
会计论文
土木工程
电子通信
食品科学
教学论文
医学论文
体育论文
论文下载
研究现状
任务书
开题报告
外文文献翻译
文献综述
范文
随机化快速选择算法的时间复杂度理论分析与实验研究(4)
算法1 SELECT
输入:n个元素的数组A[1...n]和整数k,1≤k≤n。
输出:A中的第k小元素。
1. select(A,1,n,k)
过程 select(A,low,high,k) //注释:A是包含若干元素的数组,其下标范围是[low,high]
1. //注释:p是数组A的元素个数
2. If p<44 then 将A排序 return(A[k])
3. 令 。将A分成q组,每组5个元素。如果5不整除p,则排除剩余元素。
4. 将q组中的每一组单独排序,找出中项。所有中项的集合为M。
5. //注释:mm为中项集合的中项
6. 将A[low...high]分成三组
7. case
:retuen select( ,1, ,k)
:return mm
:return select( ,1, , )
8. end case
对于以上快速选择算法的伪代码,我们进行简要的分析:首先,如果输入数组A的元素个数小于预定义的阈值44,则算法使用直接的排序方法将元素排序得出第k小元素,至于选择阈值为44的原因将在后面的具体分析中给出。接下来,把n个元素划分成 组,每组由5个元素组成,如果n不是5的倍数,则排除剩余的元素。每组进行排序并取出它的中项即第三个元素。接着将这些中项序列中的中项元素记为mm,它是通过递归计算得到的。算法的步骤6将数组A中的元素划分为三个数组: , , ,其中分别包含小于、等于、大于mm的元素。最后,在第7步,求出第k小的元素出现在三个数组中的哪一个,并根据测试结果,算法或者返回第k小的元素,或者在 或 上递归。
共4页:
上一页
1
2
3
4
下一页
上一篇:
企业IP地址优化与管理+文献综述
下一篇:
JPcap网络流量监控的设计与实现
嵌入式实时系统开发的正确选择【2027字】
三网融合及其物理网络的选择【2014字】
互联网”时代电子商务发...
粗糙集的特征选择及其分...
HEVC高效视频编码中的编码...
图像匹配快速算法的研究与MATLAB程序
利用快速K-medoids聚类算法...
公寓空调设计任务书
承德市事业单位档案管理...
中国学术生态细节考察《...
10万元能开儿童乐园吗,我...
AT89C52单片机的超声波测距...
神经外科重症监护病房患...
医院财务风险因素分析及管理措施【2367字】
C#学校科研管理系统的设计
国内外图像分割技术研究现状
志愿者活动的调查问卷表