共查询到18条相似文献,搜索用时 390 毫秒
1.
本文首先给出一个求解一类T型线性方程组的快速串行算法,它的复杂性是O(nlogn),比目前最好的O(n~2)算法复杂性要低。接着又指出了它的并行计算方案,在n台处理机的条件下,计算步数不超过O(logn),速度倍数是O(n),效率是O(1)。 相似文献
2.
周玉林 《上饶师范学院学报》2004,24(6):73-75
本文讨论了有限期作业调度问题,用计数排序、分离森林中的有效路径压缩、按秩合并方法,得到了有限期作业调度最优化算法,其时间复杂性为O(na(m,n)),m=O(n),在实际应用中是一个线性时间复杂性算法,是渐近性能最佳的算法. 相似文献
3.
李胜华 《湖北大学学报(自然科学版)》2008,30(2):145-148
对时间复杂性为O(n2)的传统直接插入排序,提出了一种多路直接插入排序算法,给出了相关算法描述及性能分析;讨论了新算法中的插入路数与时间复杂性的关系,得出了当路数为O√n时,时间复杂性有最小值O(n3/2)的结论;最后将多路直接插入排序算法与已有的一些直接插入排序算法进行了比较,结果明显优于已有算法.文中的算法思想同样适用于折半插入排序. 相似文献
4.
一类背包问题的可解性 总被引:1,自引:0,他引:1
马绍汉 《山东大学学报(理学版)》1985,(4)
本文的主要结果是,对K背包问题给出了时间、空间复杂性为O(nM~k)的拟多项式算法;证明了若P≠NP,则该问题不存在完全多项式时间ε近似算法;对动态背包问题给出了时间复杂性为O(nM~k)的拟多项式算法。 相似文献
5.
研究宽带卫星网络的拓扑结构和路由策略,设计了一个基于时空的分布式路由算法,其计算复杂性为O(1)。针对卫星移动性进行的仿真结果表明新算法能够有效确定最小时延传播路径。 相似文献
6.
在线性规划的内点算法中,宽邻域算法比窄邻域算法的数值效果好,但宽邻域算法的复杂性比窄邻域差.提出了求解线性规划问题的一个宽邻域预估-矫正内点算法,证明了该算法的迭代复杂性是O(n L),这是线性规划的内点算法中最好的复杂性结果. 相似文献
7.
周培德 《北京理工大学学报》2005,25(4):332-336
提出计算多面体面上任意两点之间最短路径的算法:近似算法、最短路径或近似最短路径算法.近似算法的思想是采用将折线不断嵌入三角形串上的方法,而另2个算法则是通过特定法线寻找三角形串,而且将这些三角形旋转到同一平面上,从而得到最短路径.前者的时间复杂性为O(n),而后者的时间复杂性分别是O(n2)及低于O(2nn2). 相似文献
8.
提出了Auction算法在无圈网络中的一种改进.在改进的新算法中,采取了新的推进(extension)方式,从而成功地降低了算法的复杂性.改进后算法的复杂性为O(m),此处m是图的弧数. 相似文献
9.
马建峰 《陕西师范大学学报(自然科学版)》1989,(2)
本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」. 相似文献
10.
11.
本文给出了拟希尔伯特阵和一般阵相乘的快速串行与并行算法。对于串行计算,时间复杂性是O((nlogn)~2),对于并行计算,在有n台处理机的条件下,其计算步数是O(nlog~2n),而效率是O(1)。 相似文献
12.
唐自立 《南通大学学报(自然科学版)》2014,(4):12-16
提出一种新的通过一棵严格二叉树的先序序列和这棵严格二叉树的结点的层数构造这棵严格二叉树的非递归算法.举例说明新算法的执行过程.对于有n个结点的严格二叉树,新算法的时间复杂度为O(n),比相应的递归算法的低,新算法的最差情况空间复杂度为O(n),与相应的递归算法的相同. 相似文献
13.
求二元关系传递闭包的新方法 总被引:1,自引:0,他引:1
二元关系的闭包运算在网络、语法分析以及开关电路中的故障检测和诊断等领域有着重要的作用 .通过求二元关系各幂的并获得关系闭包方法后来被认为是十分困难的和甚为繁琐的 .在三十多年前 ,War Shall给出了一种算法 ,使问题得以简便解决 .但是该算法存在着大量不必要的重复计算 .本文就此做了改进 .改进的算法比 War Shall的算法在时间复杂度从 O( n3)上能够降低到 O( n2 ) 相似文献
14.
基于回溯思想的算法通过系统地搜索解空间可以得到具有交货时间的n个作业的单机作业调度问题的最优解.给出一种改进算法,使得算法的时间复杂度由O(n!)降低到O(nlgn). 相似文献
15.
一个基于桶技术的平面点集Voronoi图增量算法 总被引:1,自引:0,他引:1
设计并实现了一个有效的平面Voronoi图增量算法 .该算法以翼边数据结构为基础 ,应用桶技术选择生成子并提高近邻搜索效率 ,可处理平面点集三点共线、四点共圆等退化情形 ,并具有较高的计算精度 .尽管理论上算法的最坏时间复杂性为O(n2 ) ,实验结果表明算法的平均时间复杂性近似为O(n) . 相似文献
16.
沈光星 《杭州师范学院学报(自然科学版)》2003,2(4):1-4
利用快速傅立叶变换 (FFT) ,给出了 n阶循环矩阵开平方的一个快速算法 ,计算循环矩阵的同型平方根矩阵 (平方根矩阵也是循环矩阵 ) ,证明了同型平方根矩阵的个数为 2 n ,它是关于 n的指数函数 ;计算一个同型平方根矩阵的时间复杂性为 O(nlog2 n) ;计算全部同型平方根矩阵的时间复杂性为 O(n2 n) . 相似文献
17.
圆饼装填是一个将多个芯片设计组合到一个圆饼上,构造费用通过几个设计分担而减少的过程。本文在SIMD-CREW并行计算模型下,通过修改Preparata并行排序算法及其用到的Valiant并行归并算法,给出了分配2个设计到一个包的基本圆饼装填问题BWPP的并行算法,在O(n^1.5)台处理机上,算法的时间复杂性是O。 相似文献
18.
提出了一种分块SVD图像滤波算法,与现有的SVD滤波方法相比,它有效地降低了存储开销,计算复杂度也由原来的O(n3)降为O(n2);同时这种分块SVD滤波方法具有很好的并行性,在曙光1000A上设计了并行处理算法,实验和分析都表明,其加速比接近处理机个数p. 相似文献