一个求解P_*(K)-矩阵线性互补问题的宽邻域路径跟踪算法(英)

基于预校正方法,对P*（K）-矩阵线性互补问题给出了一个迭代复杂性为O（k＋1）n2/3L）的宽邻域路径跟踪算法,算法改进了Zhang等的可行宽域路径跟踪算法的迭代复杂性;比迭代复杂性为O的小邻域路径跟踪算法为好．     

带参数可外平面图的一个算法

证明了顶点的权为参数t的线性函数,尺寸为n的可外平面图的最小顶点复盖的耗费函数的折点个数囿界于O(n~(?)),且提出了一个时间复杂性为O(n~(?))的求解算法。     

有限期作业调度问题的最优化算法

本文讨论了有限期作业调度问题,用计数排序、分离森林中的有效路径压缩、按秩合并方法,得到了有限期作业调度最优化算法,其时间复杂性为O(na(m,n)),m=O(n),在实际应用中是一个线性时间复杂性算法,是渐近性能最佳的算法.     

在QT-图中寻找最小路覆盖的方法

主要给出了QT-图（quasi-threshold graph）中两种寻找最小路覆盖的方法。假设QT-图G有m条边,n个顶点,首先,应用余图中寻找最小路覆盖的思想来解决QT-图中此类问题,其算法复杂性为O（n）;第2,根据QT-图的Tad（G）（即available-dummy tree）的构造,建立了一种解决此类问题的新算法,并给出了算法的正确性说明,它的算法复杂性为O（logn）。     

多处理器上（m,n）选择问题的一个并行算法

给出求解从任意给定的n个数据中选取m个最小(最大)者即(m,n)选择问题的一个并行算法(m相似文献   

最小-最大圈划分的近似算法

给出了求解最小-最大圈划分问题的一种新的近似算法,该算法的近似比为305p-2,时间复杂性为O（n^4）．     

P与d一致时的分族分批排序误工个数问题

研究了一类分族分批排序最小误工个数问题,给出并证明了最优排序的性质,证明了此问题是NP-困难的．对工件的到达时间和工期一致时的情形,给出了一个时间复杂性为O（mb（n/m）^2m）的动态规划算法．     

求解一类T型线性方程组的快速算法

本文首先给出一个求解一类T型线性方程组的快速串行算法,它的复杂性是O(nlogn),比目前最好的O(n~2)算法复杂性要低。接着又指出了它的并行计算方案,在n台处理机的条件下,计算步数不超过O(logn),速度倍数是O(n),效率是O(1)。     

求解多背包约束下下模集函数最大值的近似算法及其性能保证

将部分穷举法与贪婪算法相结合,给出求解多背包约束下非减下模集函数最大值的近似算法．证明了该算法的性能保证是1-e^-1,算法的时间复杂性为O（3n^4）．     

基于Grover算法的量子多用户检测

经典的多用户检测技术，其求解最优解的时间复杂度为0(2n)，这是一个NP难解问题．在Pauli算子的基础上建立量子多用户信道模型，给出利用Grover算法的多用户检测解决方法．该算法的时间复杂度为O(√2n)，并且当2n足够大时，其错误的概率趋近于0．     

拟希尔伯特阵和一般阵相乘的快速串行与并行计算

本文给出了拟希尔伯特阵和一般阵相乘的快速串行与并行算法。对于串行计算,时间复杂性是O((nlogn)~2),对于并行计算,在有n台处理机的条件下,其计算步数是O(nlog~2n),而效率是O(1)。     

最小基数箱子覆盖问题

最小基数箱子覆盖问题,是在物件大小满足一定的条件下的装箱问题．给出了一个时间复杂度为O（n）的启发式算法．     

一个预测RNA二级结构的回溯算法

本文讨论了一个预测RNA二级结构的回溯算法。该算法根据极大基配对的原则按字典顺序产生所有可能的二级结构。它的时间复杂性是O(n~2),空间复杂性是O(n)。     

关于图染色的算法

本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」.     

具有交货时间的单机作业调度问题的最优解

基于回溯思想的算法通过系统地搜索解空间可以得到具有交货时间的n个作业的单机作业调度问题的最优解.给出一种改进算法,使得算法的时间复杂度由O(n!)降低到O(nlgn).     

相交格子集合边界探寻及其Matlab实现

给出一种针对标准正六面体格子集合中探寻两个格子集合公共边界的算法,并利用这种算法在上得到相应边界图示.在两个集合个数分别为和的情况下,算法的时间复杂度以及空间复杂度均为O(mn).     

一个基于桶技术的平面点集Voronoi图增量算法

设计并实现了一个有效的平面Voronoi图增量算法 .该算法以翼边数据结构为基础 ,应用桶技术选择生成子并提高近邻搜索效率 ,可处理平面点集三点共线、四点共圆等退化情形 ,并具有较高的计算精度 .尽管理论上算法的最坏时间复杂性为O(n2 ) ,实验结果表明算法的平均时间复杂性近似为O(n) .     

由先序序列和结点的层数构造严格二叉树的高效算法

提出一种新的通过一棵严格二叉树的先序序列和这棵严格二叉树的结点的层数构造这棵严格二叉树的非递归算法.举例说明新算法的执行过程.对于有n个结点的严格二叉树,新算法的时间复杂度为O(n),比相应的递归算法的低,新算法的最差情况空间复杂度为O(n),与相应的递归算法的相同.     

求二元关系传递闭包的新方法

二元关系的闭包运算在网络、语法分析以及开关电路中的故障检测和诊断等领域有着重要的作用 .通过求二元关系各幂的并获得关系闭包方法后来被认为是十分困难的和甚为繁琐的 .在三十多年前 ,War Shall给出了一种算法 ,使问题得以简便解决 .但是该算法存在着大量不必要的重复计算 .本文就此做了改进 .改进的算法比 War Shall的算法在时间复杂度从 O( n3)上能够降低到 O( n2 )     

圆饼装填问题的并行算法

圆饼装填是一个将多个芯片设计组合到一个圆饼上，构造费用通过几个设计分担而减少的过程。本文在ＳＩＭＤ－ＣＲＥＷ并行计算模型下，通过修改Ｐｒｅｐａｒａｔａ并行排序算法及其用到的Ｖａｌｉａｎｔ并行归并算法，给出了分配２个设计到一个包的基本圆饼装填问题ＢＷＰＰ的并行算法，在Ｏ（ｎ＾１．５）台处理机上，算法的时间复杂性是Ｏ。