关于求平面点集凸包的一个O(n)时间算法的商榷

王志强等于1998年提出了一个计算平面点集凸包的新算法，并且声称该算法的最坏时间复杂度为O(n)，从而为张性时间排序提供了可能性，该文对王志强等提出的求平面点集凸包算法的时间分析提出了不同观点，进一步明确了平面集凸包算法和排序算法的时间下界为Ω(nlogn).     

求有向图必经结点的一个有效算法

本文给出在任意有向图中求必经结点的一个算法,以及对应的BASIC语言写的程序。算法使用了深度优先搜索、脱机最小值算法、不相交集的合并算法,以及能体现优先队列功能的2—3树算法,从而使算法的时间复杂性最多为O(nlogn e),空间复杂性最多为O(e),n,e分别为图的结点数和边数。当e≥nlogn时,本算法时间复杂性为O(e),它在一个常数范围内是最优的。     

电路布线问题求解的改进算法

常用的解决电路布线问题的算法的时间和空间的复杂度都是O(n2)。这里n为一块电路板的上端(或下端)接线柱的个数。现给出一种时间复杂度为O(nlogn)的新算法。改进了传统的算法。     

单向链表快速排序算法

单向链表广泛应用于动态存储结构,当前单向链表的排序算法普遍效率偏低,而平均效率最高的快速排序算法并不适用于单向链表。基于分治策略,使用递归方法,通过重新链接单向链表节点,提出了用于单向链表的快速排序算法,其平均时间复杂度为O(nlog2n),辅助空间复杂度为O(0),平均递归栈空间复杂度为O(log2n);同时,进行了算法分析和实验测试,其效率较其它单向链表排序算法有较大提高,且较传统基于线性表的快速排序算法也有一定提高。研究结果解决了当前单向链表排序效率较低的     

线对象邻接关系快速重构算法

给定向量化坐标,计算n个线对象两两邻接关系,普通算法时间复杂度为O(n*n);理论最好时间复杂度为O(C),其中C是邻接关系的基数。基于散列桶,给出了建立线对象邻接关系的快速算法,其平均时间复杂度为O(n(1+1/r)),r为算法分配的桶数量与n的比,空间复杂度为O(n)。证明了若不允许使用额外空间,则不可能使用排序算法解决该问题;给出了允许使用额外空间条件下的两遍排序算法,时间复杂度为O(n(lbn+1+2/r))。应用表明快速算法比普通算法速度提高1~3个数量级。     

位排序--一种快速排序法

众所周知,排序速度的快慢,取决于排序算法的时间复杂度和空间复杂度。因而,排序算法设计的主导思想,就是要千方百计降低算法的时间复杂度和空间复杂度。虽然计算机硬件的运算速度越来越快,但排序算法的研究仍是算法理论中的一个重要课题。已有的排序算法很多,在所有基于“记录关键字之间比较”的排序方法中,快速排序(quick sort)是平均时间性能最好的一种方法,平均时间为O（n*log n)。但是在最坏情况下,时间复杂度却很高,为O(n^2)。     

单向链表快速排序算法

单向链表广泛应用于动态存储结构,当前单向链表的排序算法普遍效率偏低,而平均效率最高的快速排序算法并不适用于单向链表。基于分治策略,使用递归方法,通过重新链接单向链表节点,提出了用于单向链表的快速排序算法,其平均时间复杂度为O(nlog2n),辅助空间复杂度为O(0),平均递归栈空间复杂度为O(log2n);同时,进行了算法分析和实验测试,其效率较其它单向链表排序算法有较大提高,且较传统基于线性表的快速排序算法也有一定提高。研究结果解决了当前单向链表排序效率较低的问题。     

快速排序性能分析

在决策树计算模型下,任何一个基于比较来确定元素相对位置的排序算法需要的计算时间是Ω(nlog2n).如果能设计一个需要O(nlog2n)时间的排序算法,在渐近的意义上,这个排序算法就是最优的.由C.A.R.Hoare发明的快速排序算法它在平均情况下需要O(nlog2n)时间.本文就该算法在最好情况下、最坏情况下、平均情况下的性能进行分析.     

基于图形硬件的双调排序算法优化

介绍一种新的并行排序算法,该算法以双调归并排序为基础,运用图形硬件的并行体系结构和二叉排序树数据结构的优点,用部分并行代替所有阶段的顺序执行,对双调排序算法进行优化.对该算法进行分析,在理论上n个序列在P个流处理器上的排序,最优的时间复杂度为O((nlogn)/p).实验测试结果表明,优化后的算法比其它基于图形硬件的双调归并排序算法所用时间短.     

基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

快速排序的一种改进算法

快速排序算法是基于关键字比较的一种性能较好的排序算法,平均时间复杂度为O(nlogn)。文章针对快速排序分治的策略和基数排序的原理,提出了一种基于基数的快速排序改进算法,论述了改进算法的理论依据和基本思想,并给出了递归形式的算法描述。改进后的算法在执行效率方面和占用辅助空间方面都有所改善。改进后算法不需要作关键字比较,特别适合大数据量的排序,具有一定的应用价值。     

深度优先稳定原地归并排序的高效算法

基于分治策略,使用深度优先的方法,提出了一种用于线性表的稳定原地归并排序算法,其时间复杂度为O(n lb n),辅助空间复杂度为O(1),递归栈空间复杂度为O(lb n),同时进行了算法分析和实验测试。实验结果表明,该算法效率较STL中的稳定原地归并排序算法有67.51%的提升,解决了稳定排序算法中要么时间复杂度高要么空间复杂度高的问题。     

最长递增子序列问题研究

本文采用分治策略和动态规划策略探讨了最长递增子序列问题的两种解法,并分析了算法的计算复杂度。结果表明,本文算法的时间复杂度和空间复杂度分别为O(nlogn)和O(n)。     

基于向量距离的词序相似度算法

手机POI搜索已经成为手机搜索的主要应用之一。该文结合手机搜索的特点以及POI数据的结构性特征采用简拼进行POI搜索。由于词序相似度是影响简拼搜索排序结果的主要因素,该文提出了基于向量距离计算词序相似度的算法。该算法采用空间向量模型作为简拼的表示方法,将提取的公共简拼映射为位置向量,进而利用位置向量间的距离计算词序相似度。通过理论分析,该算法相比基于逆序数的词序相似度算法,将时间复杂度由O(nlogn)降为O(n),空间复杂度由O(n)降为O(1)。实验结果表明,基于向量距离的词序相似度算法有效地保证了准确性,可以满足手机POI简拼搜索的应用需求,并在性能上将词序相似度的计算效率提高16.88%。     

FlashSort排序算法及实现

现在最快的排序算法是快速排序算法,它的时间复杂度达到O(n log n)。但是还有一种排序算法,就是Flashsort排序算法。它的时间复杂度达到O(n),超过了前者。FlashSort排序是基于分类的算法,它的实现思想很简单,是利用构造出来的索引来排序。举一个简单的例子,比如有一百个整数,你很容易就能把它们放在数组的正确位置上,根本不需要作任何比较。     

FlashSort排序解法及实现

现在最快的排序算法是快速排序算法,它的时间复杂度达到O(n log n)。但是还有一种排序算法,就是Flashsort排序算法。它的时间复杂度达到O(n),超过了前者。FlashSort排序是基于分类的算法,它的实现思想很简单,是利用构造出来的索引来排序。举一个简单的例子,比如有一百个整数,你很容易就能把它们放在数组的正确位置上,根本不需要作任何比较。     

一种基于线索化二叉排序树的数据流挖掘的决策树分类新算法

数据流具有数据持续到达、到达速度快、数据规模巨大等特点,这些都给数据流挖掘领域研究工作带来了新挑战,而其中分类算法更是当前的研究热点. Domingos等人在VFDT中利用Hoeffding不等式很好地解决了在数据流上进行单遍扫描获取高精度决策树的问题. Gama等人对VFDT进行扩展并实现了VFDTc,使系统能够处理连续属性,并在叶节点采用了贝叶斯分类算法使分类精度更高.基于VFDT和VFDTc,设计并实现了一种基于线索化二叉排序树的决策树分类新算法VFDTt,其主要贡献有如下3点:1)第1次设计并实现了数据流上的基于线索化二叉排序树(TBST)的连续属性处理方法.相比VFDT,VFDTt的样本插入时间复杂度由O(n2)降低到O(nlogn).当新样本到达时,VFDTc需要更新O(logn)个属性节点,而VFDTt只需要更新相应的一个节点即可. 2)改进了VFDTc连续属性的最佳划分节点选取的计算方法,使其时间复杂度由O(nlogn)降低到O(n). 3)相比VFDTc,VFDTt只需从更少的备选划分节点中选取最佳节点,备选划分节点数由O(n)降低到O(logn).     

一种基于HASH变换的循环散列分档排序算法

在数据排序问题中,各种分段快速排序算法[3～11]只有对特定的数据分布类型或者符合ΔM相似文献   

不可能差分攻击中的明文对筛选方法

基于快速排序原理,提出用于筛选明文对的基本算法和改进算法,改进算法的计算复杂性可以将由直接检测方法的O(n2)降为O(nlogn)。基于上述结果以改进算法分析对ARIA等分组密码算法的几个不可能攻击的计算复杂性,证明ICISA2008上发表的某个针对对ARIA的不可能攻击的数据筛选过程的计算复杂性远高于密钥求解过程的计算复杂性。     

3字符最长公共弱递增子串的O（nloglogn）算法

最长公共子串(LCS)和最长递增子串(LIS)是两个非常经典的基础算法问题,并且在生物信息学中已有重要应用.2006年,Brodal等人提出了最长公共弱递增字串问题(LCWIS),并且给出了2字符字母表上线性时间算法和3字符字母表上O(nlogn)时间的算法.本文中,我们提出了一种新的在3字符字母表上寻找最长公共弱递增子串(LC-WIS)的算法.该算法利用了两个成熟的数据结构:约束堆(Bounded heap)和van Emde Boas树.我们算法的时间复杂度是O(nloglogn),空间复杂度为0(n),两者都是目前为止最优的.