线性时间选择问题的教学探讨

来源 :电脑知识与技术 | 被引量 : 0次 | 上传用户:zx385213
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  摘要:针对线性时间选择问题,分别对一般情况下的算法思路和最坏情况下的算法思路进行介绍,结合教学过程和特点,通过增加递归调用的结束条件、无需改造划分函数而直接调用以及对相同划分元素进行集中排列等,对算法进行了优化和改进,增强了算法的连贯性和适用性,使学生更加直观深刻地理解和应用线性时间选择问题的算法,收到较好的教学效果。
  关键词:线性时间选择;最坏情况;基准元素;划分
  中图分类号:TP301 文献标识码:A 文章编号:1009-3044(2016)21-0087-02
  1 线性时间选择问题描述
  给定 n 个元素的集合,集合中的第 k 个顺序统计量是指集合中的第k 个(1≤k≤n) 最小元素。当k=1时,指集合中的最小元素;当k=n时,指集合中的最大元素。如何从给定的集合中找出第 k 个最小元素,被称为元素选择问题。线性时间选择问题是指在线性时间内实现元素选择。该问题在大规模数据检索和人工智能搜索方面有广泛的应用。同时该问题也是分治算法教学中的一个典型例子。
  2 实现线性时间选择的典型分治算法
  2.1 一般性选择问题的分治算法
  对于一般的选择问题,可使用RandomizedSelect(a,p,r,k)实现在期望情况下对数组a[p:r]在线性时间内选出第k小的元素。教材中的函数描述如下:
  RandomizedSelect()函数中引入随机划分函数RandomizedPartition(p,r)对数组a[p:r]进行划分,该函数以a[p:r]中的一个随机元素作为划分基准,将原数组划分为两个子数组a[p:i]和a[i 1:r],使得第一个子数组中的所有元素全小于等于第二个子数组中的所有元素。通过RandomizedPartition()函数的返回值i可以计算出第一个子数组的元素个数j,根据j值与k值的大小比较,可以判断出所要求的第k小的元素是落在哪个子数组,从而继续递归调用RandomizedSelect()函数对缩小了查找范围的子数组进行查找。直至待查找数组只有一个元素,则该元素就是要查找的a[p:r]中第k小的数。
  该算法的平均性能很好,可以在O(n)时间内找出结果。但是,如果每次产生的划分基准都是数组中的最大值或最小值,则算法在这种最坏情况下可导致O(n2)的时间效率。
  2.2 最坏情况下的选择问题的分治算法
  对于每次划分,如果能在线性时间内找到一个划分基准,以这个划分基准所划分出的两个子数组的长度都至少是原数组长度的常数倍(0<<1),那么就可以在任何实例的情况下都能避免前述最坏情况的发生,保证了算法一定能在线性时间内找到结果。函数Select()按照这个思路实现线性时间选择。
  Select()函数中,将数组a[p:r]分成?n/5?个组,每组5个元素,最后一个组可能不足5个元素。对每个组分别排序,并取其中位数,共有?n/5?个中位数。调用Select()函数求这?n/5?个中位数的中位数x。以x作为划分基准对a[p:r]进行划分,通过Partition()函数的返回值i可以计算出划分后的第一个子数组的元素个数j,根据j值与k值的大小比较,可以判断出所要求的第k小的数是落在哪个子数组,从而继续递归调用Select()函数对缩小了查找范围的子数组进行查找。直至待查找数组的数据量小于75,则直接对其排序,并返回第k小的元素。
  若待查找的数据量小于75,则Select()函数用于排序的时间为常数C。若数据量大于75,设Select()函数共需要T(n)时间,则查找中位数的中位数x需要T(n/5)时间,由于以x作为划分基准所得到的两个子数组都不超过3n/4个元素,故递归调用Select()函数继续查找的时间至多为T(3n/4)时间。因此T(n)=O(n)。
  3 教学内容探讨
  可对2.1中的RandomizedSelect()函数和2.2中的Select()函数进行改进,以优化算法和有利于学生更为深入连贯地学习线性时间选择问题。
  (1)在计算j值后判断相应划分点是否就是所求的第k小元素
  RandomizedSelect()和Select()函数中,对a[p:r]进行划分后,都要计算划分点a[i]是数组的第几小,计算结果为j。函数中可以插入语句,比较j值与k值是否相等,若相等,则说明划分点a[i]就是所要查找的第k小的元素。因此无需再继续进入下一轮的递归调用,返回a[i],程序结束。
  (3)对Select()函数作进一步改进
  以x作为划分基准对a[p:r]进行划分后,可以在线性时间内将与x相等的元素集中排列在一起,并记录这些元素的起始下标i1和结束下标i2,若i1-p 1≤k≤i2-p 1,则说明x就是所要查找的第k小的元素。因此无需再继续进入下一轮的递归调用,返回x,程序结束。否则,进一步缩小查找范围,递归调用Select()函数进行查找。
  4 结语
  如何在最坏情况下实现线性时间选择是分治算法里相对较难理解的问题。本文先介绍一般情况下线性时间选择的算法思路,再介绍最坏情况下线性时间选择的算法思路。文中针对教材所提出的算法,分别从算法优化方面和算法适用性方面进行了改进,从而让学生能够更加直观深刻地理解和应用线性时间选择问题的算法,收到了更好的教学效果。
  参考文献:
  [1] 王晓东.计算机算法设计与分析[M].北京:电子工业出版社, 2012.
  [2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
  Introduction to Algorithms [M]. Second edition. MIT Press, 2006.
其他文献
以木薯淀粉为原料,醋酸酐为酯化剂制备淀粉醋酸酯,考察制备条件对取代度的影响。实验结果标明:取代度随反应体系pH升高而增加,在pH9时达到最高值,之后下降;温度升高,取代度随
技术反哺是工业反哺农业的造血机制,本文在对技术反哺进行定义的前提下,剖析技术反哺农业的现实基础,探析工业对农业的直接技术反哺路径和间接技术反哺路径,并有针对性地提出技术
结合我国出口企业所面临的技术性贸易壁垒实际情况,根据系统输入要素、转换要素、输出要素建立了由2个一级指标、3个二级指标、28个三级指标构成的评价指标体系,构建了模糊神
受经济市场化、信息迅捷化及思想多元化的影响及以往思想品德教育模式的僵化、单一,加之一系列庸俗社会学、功利主义以及享乐主义的侵蚀,当前某些大学生的社会责任感呈现出了
文章分析了档案管理工作与独立学院评估的相互促进关系,论述了独立学院评估工作对高校档案管理工作的促进作用。
众所周知,教育的关键在教师.教师素质的提高是教育质量提高的根本之所在.函授教育是提高教师素质的途径之一.通过函授学习使初中教师达到合格的学历水平是我校师资培
文化产业的发展不仅需要政策支持,更需要法律制度的规范和指引。河北省文化产业还存在立法不完备、立法滞后、立法层级低、理念陈旧等不足之处,还未形成健全的体系。地方政府只
不管是从网上下载图片,还是使用数码相机拍摄照片时,得到的都是风格固定的静态图片。观赏的时间长了,会让人产生枯燥单调的感觉。俗话说,笑一笑十年少。看到有趣滑稽的图片,
邓小平文选第三卷的发行,是我国人民生活中的一件大事.这本书不仅仅反映了关于建设有中国特色的社会主义理论的形成和发展过程,而且生动地记载了全国人民已经做和正在做的重
在逐步建立社会主义市场经济体制的过程中,人们的思想观念、价值取向、行为方式等都发生了很大的变化.高校中的青年学生做为社会中的一分子,当然也受到了各种思想的冲击.如何