多队列快速排序

快速排序算法的平均时间小于所有已知的O(nlogn)排序算法。它的平均时间是O(nlogn),最坏情况为O(n~2)本文提出的算法对n个元素的排序时间为O(nlogm),其中其最佳性能为O(n)在M 16计算机上运行的结果符合文中给出的算法分析     

右完全树和右完全分类算法

本文讨论了右完全树及其性质,并把它用于右完全分类算法。其数据结构与堆分类(Heapsort)同样简明,不但具有最优的O(NlogN)阶最坏情况时间复度,而且当输入序列为已分类或几乎分类时,其时间代价仅为O(N)阶,明显优于堆分类的O(NlogN)阶。     

一个具有平均复杂性的SAT问题

最坏复杂性到平均复杂性的归约已被研究很多年。很多NP困难问题是最坏复杂性的。distNP类是平均复杂性的NP类,且有完全问题。LIVEN N证明了所有自然的NP完全问题都有平均复杂性的形式,但是他给出的概率分布是不自然的。在格问题方面,AJTAI和REGEV O分别提出了平均复杂性的困难问题,即短整数解问题(Short Integer Solution,SIS)和带错误学习问题(Learning With Errors,LWE)。给出一个可以归约到判定对于一个NP完全问题是否存在多项式时间算法,对值为1的实例给出一个见证,并且对值为0的实例给出一个归结辩驳的具有平均复杂性的SAT问题。本文方法是将求解NP完全问题的多项式时间算法的存在性转化成SAT问题的一组实例。同时也给出了这个问题的一些变形问题。     

ABD表的存在及构造

组合Hash是一种对多重属性文件进行部分匹配检索的最优算法,而ABD(Associative Block Design)技术乃是寻求一种在期望与最坏情况下时间复杂性都令人满意的实用最优算法的关键。本文在文[1],[2]的基础上,给出了ABD表的一个存在性定理,并对相当大的一类ABD表给出了构造方法。     

充分利用局部有序的快速排序

1984年R.G.Dromey提出了在快速排序中利用部分有序的算法。本文对他的有序性概念进行了扩充。改进后的算法充分利用了排序数据的有序性。算法的最佳性能为o(n),最坏情况为O(n~2)。因此本算法优于快速排序和TRANSORT。     

可采纳搜索算法最坏复杂度的下确界

本文通过证明可采纳搜索算法的最坏复杂度不可能小于M(M是被搜索图的大小)和可采纳的搜索算法S的最坏复杂度等于M,得出以下结论:可采纳的搜索算法的最坏复杂度的下确界是M。本文还指出了L.Méró关于“无普遍最优算法”的证明中的错误,并给出了新的证明。     

快速合并分类法在微机上的实现

本文介绍了合并分类法在微型计算机上的实现,合并分类法比一般的分类方法(如冒泡法、二分法等)要快速得多,程序也易于编制。此算法是属于O(n log_2n)级的分类法。它的时间复杂性为nlog_2n-n 1,这个值已经和分类问题的理论下界相当接近。本法在某些实际工作中已经得到了应用,并已收到了快速的效果。文中给出了在微型计算机CROMEMCO上实现本算法的BASIC程序,使用时可把本程序作为一个子程序加以调用。     

立体堆分类算法设计与分析

本文在完全立体二叉树的基础上,提出了立体堆的分类方法,并对它的算法实现进行设计与分析,得出了立体堆分类方法在最坏情况下的时间复杂性,从而减小了堆分类方法的时间复杂性的常数因子。     

脉冲拥挤型最坏花样测试码的效率计算与生成

本文对NRZI和游程长度受限码RLLC码型的脉冲拥挤型最坏花样测试码进行了研究,引述了反映幅度变化和峰值位移基元最坏花码的一般模式和具体数据序列。给出了计算测试码效率的模型和算法。根据J.L.Massey综合算法原理,提供了一种求解生成给定最坏花码序列的最短线性反馈移存器的算法和步骤。最后,给出了16位NRZI的最坏花码序列的特征多项式及产生器框图。     

基于降阶的最小生成树快速算法*

在分析最小生成树问题数学性质的基础上,给出了一种基于降阶技术的快速最小生成树算法。该算法采用降阶技术,大大加快了算法的求解速度,在最坏情况下算法的时间复杂度为O(m);另一方面,算法易于找到问题的全部最小生成树。     

快速排序性能分析

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

基于流水光总线阵列上的快速可扩展并行排序算法

在Y．Pan提出的基于流水光总线阵列模型(LARPBS)上使用N个处理器对N个元素进行排序在最好情况下以O(logN)时间，最坏情况下以O(N)时间完成的并行排序算法的基础上，提出了一种LARPBS模型上的可扩展的快速并行排序算法，对N个元素进行排序，使用p(1≤P≤N)个处理器在最好情况下以O(NlogN／p)时间，最坏情况下以O(N^2／p)时间完成排序。另外还提出了一种LARPBS模型上改进的快速高效并行排序算法，该算法对N个元素进行排序使用N个处理器在最好情况下以O(log√N)时间、最坏情况下以O(√N)时间完成排序。     

受启动空间约束的装箱问题

提出了一种带有启动空间的约束装箱问题(start-up bin packing problem,简称SBPP),即不同类型的物品放入同一箱子中需要一个启动空间.该问题在工作分配、任务调度和日常生活中的包装等问题中有着广泛的应用背景.给出了一个求解SBPP的线性脱线算法C-NF,其最坏情况渐近性能比为2,与启动空间的大小无关.对该算法的平均性能进行了实验分析.另外,还分析了SBPP的在线特性,指出大量的经典在线装箱算法应用于SBPP都不存在确定的最坏情况渐近性能比,也给出了一种具有确定的最坏情况渐近性能比的在线算法.     

基于Bucket Sort的快速属性约简算法

利用桶排序思想设计了一个求解U/C的算法,其时间复杂度降为O(∣C∣∣U∣).由此,给出一种无需求解正域便能判断正域是否变化的方法.基于以上方法,提出一种快速属性约简算法.该算法的求解策略是在每次迭代过程中求解决策表相对核,如果在某次迭代过程中找不到这样的核属性,则任意排除一个条件属性.最后通过实验分析了该算法在最坏情况下的时间复杂性,其复杂性降为O(∣C∣2∣U/C∣).     

典型“稳定婚姻问题”的简明矩阵算法实现

对于典型"稳定婚姻问题",本文借助矩阵(二维数组)给出了一种简明的实现方法。在本算法中,所采用的存储结构和实现方法灵活巧妙,通俗易懂,方便实现;而且用于存储所要处理数据的内存空间相对于其他一些算法节省了一半,空间复杂度为O(1);由于存储结构的巧妙性,算法的时间复杂度在最好的情况下为线性时间N,在最坏的情况下为O(N2)。     

顺序统计问题研究

顺序统计问题是算法设计与分析中的一个典型的问题,即从n个元素中选出第k个最小元素。文章采用分治算法解决顺序统计问题,给出了通用算法,并对算法的复杂性进行了分析和讨论。对于子序列长度大于5的情形,该算法的最坏情形的时间复杂性为O(n)。     

一种二值图象欧拉数的并行快速算法

本文给出了一个求方格(square grid)上二值化图象欧拉数的并行快速算法,并通过将 方格上的二值图象转化成数字图来引用图论方法对该算法进行了证明,且给出了若干实例以 说明算法的有效性.     

最坏情况下#3-SAT问题最小上界

最坏情况下#SAT问题上界的研究已成为一个热门的研究领域.#SAT问题的时间复杂性是根据问题实例的大小所组成的函数计算所得.#SAT问题实例的大小不仅依赖于变量的数量,还依赖于子句的数量.以子句数量为参数研究#SAT问题在最坏情况下的上界,不仅可以从另一个角度衡量算法的好坏,而且在某种程度上更能准确地反映出算法的性能.首先从子句数量的角度证明了之前提出的基于扩展规则的模型计数算法(CER算法)的上界O(2m),其中m是公式中子句的数量.为了提高#3-SAT问题的求解效率,采用了多种分裂规则,进一步给出了一种基于Davis-Putnam-Logemann-Loveland(DPLL)的#3-SAT算法MCDP.通过分析该算法得到了以子句数量为参数的#3-SAT问题在最坏情况下的上界O(1.8393m).     

有色装箱问题的在线近似算法

有色装箱问题是经典装箱问题的推广,它在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景,提出了求解有色装箱问题的KC－A算法,它首先对输入物品进行分类预处理,然后在同一类内部使用经典装箱问题的近似策略A,给出了KC－A算法最坏情况渐近性能比的下界,分析了当选用的算法A是著名装相算法NF,FF,BF,WF时KC－A算法的最坏情况渐近性能比和平均性能比,给出了实验结果,并指出KC－FF表现出相对更好的实验效果。     

算法复杂性平滑分析的研究进展与展望

有很多算法其最坏情况复杂性很坏 (甚至是指数阶的 ) ,但在实际应用中却很有效 其中一个典型代表就是求解线性规划问题的单纯形算法 最近 ,Spielman和Teng提出了算法的平滑复杂性概念及算法复杂性平滑分析方法 ,对上述矛盾给出了合理的解释 ,在理论计算机科学界引起了极大的关注 为此 ,做了以下工作 :介绍算法复杂性平滑分析的基本概念 ;介绍两年多来算法复杂性平滑分析主要的研究进展 ;从实际应用出发提出一个更合乎算法复杂性平滑分析思想的随机扰动模型 (简称TSSP模型 ) ,克服“PartialPermutation”随机扰动模型的不足 ,并证明在TSSP模型下快速排序算法的时间平滑复杂性为O(2λn×log2 (n) ) ,其中λ是随机扰动幅度大小 最后 ,对算法复杂性平滑分析的研究提出了展望