一种基于有序双端链表的高效排序算法

本文提出一种新的基于有序双端链表的比较排序算法,即ODListsort(ordered double-end linked list sort)算法。该算法首先要定义一个可共存的链表最大数量,然后通过生成链表、根据规则插入数据以及合并操作来对数据集进行排序。在ODListsort算法中,数据元素是以链表形式进行动态内存分配的,因此它比一些经典的排序算法性能更优。实验结果表明,对于随机数据集,ODListsort排序与快速排序的速度接近,比归并排序、选择排序、插入排序以及冒泡排序的速度更快;对于有序数据集,ODListsort排序的效率远超快速排序,略高于归并排序。     

一种基于数据块交换的快速稳定原地归并算法

与其它排序算法相比.二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个 有序子表,经典算法有2种/第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动/第 二种算法是原地的.但完成归并需要O(m+n)次比较和O(m*n)次移动,提出了一种基于块交换的快速 稳定原地二路归并算法.实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数.     

KNA算法计算单零点多项式全部零点的复杂性

证明用KNA算法计算n次单零点多项式全部零点所需的多项式计值次数不超过O(n~3 log_2(n/ε)),其中ε是计算精度。     

Nasm汇编器的数据存储设计与实现

数据存储在汇编器中极为重要,好的数据处理方式,可以极大的提高汇编器的编译速度。文中根据链表和树的特点,针对Nasm汇编器的数据存储方式,设计了相应的算法,使汇编器中的顺序存储和随机存储操作性能达到最优。     

超立方体中过k个指定点的最短路径

利用超立方体的拓扑结构,基于其内部节点编码的特点,分析研究得到在n维超立方体Qn中任意两节点s、t之间经过k(kn)个指定点的最短路径算法.该算法共包括了十个步骤,在最坏的情况下执行2n~2+2n(n~2+2)次运算,算法的时间复杂度为O(n~3),属于多项式计算.     

对最大团问题的HEWN算法分析

对最大团问题的HEWN(hierarchicaledge-weightnetwork)算法进行了复杂性分析.首先通过分析HEWN的结构特点和所需进行的操作,设计了一种实现HEWN算法的数据结构,指出了在HEWN算法中HEWN的存储宜采用邻接多重表和二叉链表相结合的链表表示法,然后从HEWN的存储结构入手,剖析了HEWN的构造过程,在剖析过程中,通过与MCST(maximumcompletesub-graphtree)比较,指出了当2j>n时潜在的、指数的生成和修改GM的次数存在于HEWN算法中.因而,HEWN算法的时间复杂度是指数的,而不是O(n8.5).     

多步无限撤销及恢复算法与实现

在传统与改进2种情况下对undo及Redo算法的需求作了详细分析,结合数据文档编辑为每种情况的解决给出了一套完整的算法,并对无限制撤销恢复的多步算法给出了实例验证.直接借助或使用该方案可以提高软件开发性能,并增强软件应用的灵活性.此外,使用链表顺序存储结构处理树形存储结构,解决了操作序列中出现多叉的关键问题.     

一个拟就地稳定归并排序算法

为了降低经典归并排序算法O（n）的附加空间并保持稳定性,提出一个新的拟就地归并算法.介绍了根据移动次数导出的段长关系进行选择的原理,给出了相应的归并及归并排序的C语言算法,用大量随机序列进行了排序对比测试;测试组数自动选取,拟合结果为比较次数约为20.13n ln （n）＋1.24n ln（n）-1.22n ,移动次数约为20.655n ln （ n ）-0.89nln（n）＋2.6n、附加栈空间O（ln（n））.得益于算法的简便性,附加程序开销小,在测试范围内实际时空耗费在同类算法中有明显优势.     

MapReduce模型下增量重复数据检测方法

针对重复数据检测过程中增量数据重复值检测问题进行分析,在基本近邻排序算法基础上,提出增量近邻排序比较算法。该算法通过跳动窗口形式比较相邻数据,大大减少了数据比较次数;同时引入MapReduce模型对该算法加以改进以提高其海量数据处理的能力。实验表明,改进后的增量近邻排序比较算法在保证检则结果准确的前提下,能够有效提高增量数据重复检测的速度,并且算法具有较高的稳定性,更适应海量数据环境中重复数据检测任务。     

一种改进的基于无链表SPIHT的图像压缩算法

 SPIHT算法以其简单高效而著称,但由于LSP、LIP和LIS 3个链表的使用,内存需求量大,且需要动态分配或删除链表节点;另外,排序阶段存在的重复扫描也严重影响了算法的效率和性能,因此算法不易在硬件平台上实习,也不适用于低内存和实时应用场合。本文针对SPIHT算法的不足,提出了一种改进的无链表SPIHT算法。首先,在排序阶段加入对A类集合的分类判断,优化了码流输出,提高了压缩性能;其次,在存储重要信息时,算法以状态标识矩阵代替链表,既节约了内存开销也避免了内存的动态管理,最大输出位数和集合极值矩阵的使用则减少了扫描次数,提高了运行效率。     

有限群上几个问题的算法及复杂度分析

本文讨论有限群上几个计算问题。我们设了一个O(n~2)时间的算法去查找n阶Abel群的基底(把n阶Abel群分解为循环P群的直积)。给出了复杂度为O(n~2log_2n)的n阶Abel群的检验算法。证明了n阶Abel群的同构检验可在O(nlOg_2n)时间内完成。最后,我们讨论定义在有限群上的旅行售货员问题:证明了该问题是NP完全的,并给出了一个O(m·n~2·2~n)时间的算法求解它。     

冒泡排序算法的分析与改进

冒泡排序算法有两个优点：1＂.编程复杂度＂很低,很容易写出代码;2.具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列,但当需要排序的数据较多且无序时,冒泡排序算法的时间复杂度较大,比较次数较多,本文提出了一种冒泡排序算法的改进方法,可以大大减少比较的次数,降低算法的时间复杂度。     

几种排序算法在链式存储结构上的递归实现

排序是程序设计中常用的一种操作,递归是一种重要的程序设计方法.探析了几种常用的排序算法在链式存储结构上的递归实现,包括基本思想、C语言函数源代码及详细注释,并与顺序存储结构上的算法实现进行了性能比较,以便于学习者熟练掌握链式存储结构上的递归程序设计,并为排序算法选择合适的存储结构提供借鉴.     

多路插入排序算法

对时间复杂性为O(n2)的传统直接插入排序,提出了一种多路直接插入排序算法,给出了相关算法描述及性能分析;讨论了新算法中的插入路数与时间复杂性的关系,得出了当路数为O√n时,时间复杂性有最小值O(n3/2)的结论;最后将多路直接插入排序算法与已有的一些直接插入排序算法进行了比较,结果明显优于已有算法.文中的算法思想同样适用于折半插入排序.     

TOEPLITZ矩阵、HANKEL矩阵求逆的快速算法

W.F.Trench 在 T 为对称正定矩阵的条件下给出求 T~(-1)、H~(-1)的快速算法.计算复杂性为 O(n~2)(n 为矩阵阶数).S.Zohar 进一步研究了 W.F.Trench 的算法,且把对称正定的条件减弱为强非奇,计算复杂性仍为 O(n~2).设{e~(j)}_(j=0)~n 是 n+1维欧氏空间 C~(n+1)的标准基,     

找K个最小生成树的并行算法

基于SIMD 机器——一种可以同时读但不可同时写的共享计算模型(CREW-PRAM)给出了找K 个最小生成树的并行算法,此算法需O(log~2n+Klogn~*)时间及O(n~2)处理器;而基于可以同时读、写的更强计算模型(CRCW-PRAM),求K 个最小生成树仅需O(Klogn)时间及O(n~2)处理器,这里n 是图的顶点数.     

基于向量空间的专利类比挖掘算法

新技术在进行技术突破时,很难找到创新点和方案。针对这一难题,提出一种基于向量空间的专利类比挖掘算法。首先,从源数据中获取描述功能和属性的专利技术方案(PSC),建立基于PSC的TF-IDF值的向量空间模型(VSM);然后,根据专利文献间的信息距离制成基于PSC术语的专利地图;最后,分别对PSC进行创新性分析,根据分析结果用类比的思想进行新技术的创新。本文算法的时间复杂性为O[(n~2+n)/2],低于对比算法的O(n~2)。以无线充电技术专利和无线传感技术专利文献为源数据,实验结果表明,所提出的算法比对比算法能更有效地获取更具有创新性的创新方案。     

无线传感器网络增配节点实现双连通并优化中继路径

对所有节点有统一通信功率和传输半径的无线传感器网络,用平面无向图建模。提出一个基于广度优先的O(n~3)多项式时间搜索算法来发现无线传感器网络中的双连通分量,继而确定网络中所有关节点,然后提出一个最坏情况有O(n~2log(n/3))多项式计算时间的贪心算法来增加尽量少的节点以实现网络双连通,同时,增配节点形成的新路径有助于减少部分节点到汇聚节点的中继跳数。实验结果也验证了以上算法的效果。     

一种基于数据块交换的快速稳定原地归并算法

与其它排序算法相比,二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个有序子表,经典算法有2种。第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动。第二种算法是原地的,但完成归并需要O(m+n)次比较和O(m×n)次移动。提出了一种基于块交换的快速稳定原地二路归并算法。实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数。     

信息熵与支持向量的关系

标准支持向量机由于具有O(n~3)的时间复杂度和O(n~2)的空间复杂度,影响了其在海量数据集上的应用,而对支持向量机新模型的研究则最有可能取得一些突破,从而彻底解决上述难题。介绍新模型的研究现状的基础上将信息熵引入到支持向量机建模中,重点分析数据的信息熵分布规律和支持向量数据及其熵值的关系,进一步构造了信息熵支持向量机算法,最后给出了相关实验,初步的实验结果显示信息熵支持向量机具有较快的分类速度。