基于分布计数的基数排序方法的研究

排序是计算机科学中一个非常重要的问题。提出了一种基于分布计数的基数排序方法,给出该算法定义、算法描述、算法正确性证明和算法分析;讨论了基于该排序算法几个关键问题的解决方法。算法理论分析和实验结果研究均表明该算法时间复杂度为O（N）,速度优于快速排序,是一种高效的排序方法。     

基于比较操作的排序方法的讨论

为了查找方便,通常希望计算机中的表是按关键字有序的,因为有序的顺序表可以采用查找效率较高的折半查找法查找,因此,研究各种排序方法是计算机工作者的重要课题之一。从基于比较操作的各种排序方法的具体实现算法、算法执行的效率等几个方面进行分析研究。最后提出了它们的共性,即基于比较操作的排序方法的分析与研究,主要是执行效率的研究。     

解决"计数到无穷"问题的改进方法

提出了一种改进的方法来解决距离矢量算法中的"计数到无穷"问题.这一方法给"简单分裂水平线"(simple split horizon)方法增加了一条新的规则:如果路由器A发给它的相邻路由器B的路由更新信息中不包含某些目标网络的条目,那么路由器B认为经过路由器A这些目标网络是不可到达的.     

一种基于检索树的改进计数最近邻分类新算法

计数最近邻分类算法是一种以数据格论为理论依据的新分类算法,其优越性在于能不经转换地处理各种混合数据.本文在阐述和分析该算法的基本原理后,发现该算法的计算效率及存储效率有待改进提高,因此我们提出了一种基于检索树的改进计数最近邻分类新算法,其主要思想是通过构建检索树以减少重复数据的计算量,并以此提高算法的计算效率和存储效率.通过利用国家863项目数据集和多个UCI 公共数据集的综合测试,结果表明该新算法在具有大量重复数据的应用环境中效果明显,具有较高的计算和存储空间效率.     

基于B方法的TCP协议形式化研究

协议的规格说明主要是以自然语言描述的,对其进行形式化的目的是精确描述协议,减少开发人员对协议规格说明理解的偏差.B方法可产生简明、精确、无歧义且可证明的规格说明.适合对协议进行形式化描述和一致性测试.本文详细地介绍了使用B方法对TCP协议进行形式化,并据此生成了测试用例,提高了TCP协议一致性测试的质量和可靠性.     

基于自适应聚类的图像配准方法

针对现有的特征点匹配方法存在计算耗时的缺点,无法满足实时处理的要求.本文提出一种基于自适应聚类的图像配准算法.该算法根据视差约束条件,对候选匹配点对粗筛选,删除大部分错误匹配点,实现了快速的图像配准.实验结果表明,在保证算法正确性的同时,提高了整体算法的速度.     

基于积分图像的灰度分布标准化快速算法*

在积分图像基础上提出和应用平方积分图像,实现了一种计算速度与图像窗口大小无关的快速灰度均值和方差算法.应用该算法,结合对灰度分布标准化近似计算公式的变换,实现了图像窗口灰度分布标准化的快速计算.实验证明,当需要对一幅图像的大量图像窗口进行灰度分布标准化时,这种算法对提高计算速度十分有效.     

基于贝叶斯算法的垃圾邮件过滤的研究

本文介绍了一种朴素贝叶斯算法的实现方法,并介绍了涉及到的文本特征选取、朴素贝叶斯分类器等关键技术.最后,文章给出了垃圾邮件过滤的实验结果.结果表明,该方法对于垃圾邮件的识别,具有良好的效果.     

基于仿真的电路故障知识获取方法研究

故障知识获取是基于知识的电路故障诊断方法的瓶颈问题,严重限制了电子设备智能诊断系统的发展.该文首先总结了通过故障仿真获得故障知识的一般过程,提出了基于仿真技术的故障知识获取方法,介绍了减少仿真工作量和充分隔离故障的有效方法,对主要的组成部分和功能进行了详细描述.该方法能够自动调用外部电路仿真软件对故障进行仿真,并从仿真结果中提取有用信息形成故障知识.     

基于均匀设计的基因表达式编程算法研究

提出了一种基于均匀设计的基因表达式编程的进化算法(Uniform-Design Genetic Expression Programming,简称UGEP),新算法借助均匀设计的全局均匀分散性对初始种群的产生和杂交算子进行了改进,分别设计了基于混合水平均匀表的初始种群构造法和自适应的多亲杂交均匀算子.理论分析证明UGEP具有全局收敛性,且收敛速度也优于经典的GEP.在解决函数拟合、时间序列预测等实际问题中与同类算法进行了比较,在各项实验指标上均体现出了新算法的优越性.     

基于OpenCL的双GPU基数排序算法

为提高基数排序算法在异构并行平台下的资源利用率和算法加速比,提出基于OpenCL的双GPU基数排序算法。通过研究并行基数排序思想,以Y485P作为实验平台,使用OpenCL技术首先实现单GPU的基数排序算法,之后实现负载平衡的双GPU基数排序。测试结果表明,在使用单GPU时加速比为1.3x,使用双GPU时加速比为2.32x。     

基于基数排序的集成服务优先队列算法

传统的服务质量(QoS)算法分为差别服务和集成服务两种,前者提供相对的服务质量保证,而后者则可以提供绝对的服务质量保证,二者最终都可以归结为优先队列算法。在核心路由器中QoS对优先队列的要求比较高,差别服务需要提供OC-768(40Gbps)线速、很大的有效排队长度和较小的最小时延。集成服务除了上述要求还需要很大的优先级数目。受到基数排序算法的启发,论文设计了一种基于基数排序的适用于集成服务的优先队列算法,具有以下特点:(1)带宽可以达到OC-768线速,优先级数目和有效排队长度不受限制,最小时延可以接受。(2)结构比较简单,不需要非常复杂的电路设计。     

超快速排序算法

快速排序算法结构简单,平均性能较佳;基数排序性能较稳定。结合快速排序和基数排序,提出超快速排序算法,通过理论分析和实验表明,新算法的性能优于快速排序算法和基数排序算法。     

两趟插入排序算法设计

提出了一种两趟插入排序算法,该算法容易理解,排序时间短,适用于大批量数据的排序。     

桶外排序算法的抽样分点分发策略

计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序比赛Indy组冠军.     

二维表快速排序的复杂度分析

在假设二维表数据的排列服从均匀分布的条件下,分析了用快速排序方法对二维表进行排序的过程,给出了整个排序过程的时间复杂度和空间复杂度,得到的平均时间复杂度(O(n×(m 1ogn)))低于已有文献中对二维表排序的时间复杂度(O(m×n×log n)),其中,m是二维表的关键字个数,n是二维表的记录数.仿真实验说明了文中结论的正确性.这一结果,将有助于进一步设计高效的海量数据分析方法.     

循环插入排序法

文章提出了一种循环插入的排序方法。给出了算法思想、算法描述、算法分析和实验结果。其理论意义是改进了一类时间复杂度为O(N2)排序法的时间复杂度,其实用价值是该排序法在一类时间复杂度为O(N2)排序法中排序效率较高的,其平均排序速度比直接插入排序法、选择排序法、冒泡排序快50%～63%。     

二路归并排序的链式实现方式

本文就《数据结构》课程中两路归并排序的算法的特点进行了分析,并提出了一个改进空间复杂性和时间复杂性的两路归并排序的算法。     

基于数组的桶排序算法

经典桶排序算法以链表形式实现"桶",处理均匀数据效率很高,是O(N)算法 .但对极不均匀数据则退化成低效的O(N2)插入排序 .讨论了记录携带附加数据的计数排序算法,将"桶"实现为顺序数组,避免链表的动态内存分配直接提高算法效率,并允许快排等O(N log N)算法处理桶内数据 .对均匀数据仍然保持O(N)时间复杂度,对极端不均匀数据则只退化为O(N log N)的原算法 .对一般非均匀数据,证明数组桶排序算法总体性能高于经典算法 .均匀数据实验表明,桶排序算法明显优于Linux下标准qsort系统调用,且数组桶排序算法效率更高 .而在非均匀的正态数据实验中数组桶算法性能下降明显小于经典桶排序,总体效率仍然优于qsort的直接应用 .