最少比较排序问题中S(15)和S(19)的解决

来源 :计算机科学与探索 | 被引量 : 0次 | 上传用户：llljjjxxx7

【摘要】

：

最少比较排序问题就是要研究在最坏情况下,对n个元素完成排序所需要的最少比较次数S(n).1965年M.Wells用穷举法证明了S(12)=30.2002年和2004年,M.Peczarski通过计算先后得到S

【作者】

：

成维一刘晓光王刚刘璟

【机构】

：

南开大学信息技术科学学院,南开大学信息技术科学学院天津300071,天津300071

【出处】

：

计算机科学与探索

【发表日期】

：

2007年3期

【关键词】

：

计数算法最坏情况线性扩展排序问题计算穷举法并行机证明元素设计南开基础 minimum-comparison sorting optima

【基金项目】

：

国家自然科学基金，天津市科技发展基金，南开大学校科研和教改项目

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

最少比较排序问题就是要研究在最坏情况下,对n个元素完成排序所需要的最少比较次数S(n).1965年M.Wells用穷举法证明了S(12)=30.2002年和2004年,M.Peczarski通过计算先后得到S(13)=34,S(14)=38,S(22)=71.文章在Wells算法和Peczarski算法基础上,设计了一个新的PS算法,并改进了线性扩展计数算法,在并行机'南开之星'上计算得到S(15)=42,S(19)=58.

其他文献

刍议高中物理演示实验教学

物理是一门实验性较强的学科。提高物理实验教学的效果不仅可以激发出学生的学习兴趣,还可以让学生从心里转变对物理的看法,从而提高学习质量。通过进行演示实验教学提高学生

期刊

高中物理演示实验教学研究

从不确定数据集中挖掘频繁Co—location模式

把挖掘频繁co—location模式的经典算法Join—based算法扩展到了UJoin—based算法，解决了从不确定数据集中挖掘频繁co—location模式的问题。针对UJoin—based算法中ED（expecte

期刊

不确定数据co—location模式UJoin—based算法边界矩形剪枝三角不等式剪枝uncertain data co-location pat

冷冻豆腐制作技术

期刊

动脉硬化