首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 122 毫秒
1.
针对银行业务管理、高考成绩统计、气象资料整理等一类特殊“汇总”排序问题。文中提出了一种以映射、链接和归并为基础的新排序算法-映射归并排序算法(以下简称为“映射归并排序”),给出了该排序算法的描述、时间复杂度分析及用C语言编写程序进行算法比较的实验结果。算法分析和实验结果都表明:映射归并排序方法和待排序数据分布无关,其时间复杂度仅为O(N);而且在处理上述大规模“汇总”排序问题时,映射归并排序速度明显优于Flash Sort,Proportion Split Sort,2-路重复的K路归并排序和直接K路归并排序等算法。  相似文献   

2.
查找第K个元素的问题在计算机查找技术中占有十分重要的地位,这个问题的最直接解法是先将序列排序,从而能得到第K个元素,最少需O(nlogn)次比较,即时间复杂度为O(nlogn).比较好的方法是采用分治策略解决该同题,但其最坏时间复杂度为O(n^2),平均时间复杂度为O(2n).本文提出一种Byte解决第K个元素问题的算法,该算法的平均时间复杂度为O(n n/255),优于以前对该问题的求解方法,而且该算法可以适用于由整数、浮点数、无符号整型数、双精度数和字符型数构成的超大数集.  相似文献   

3.
分别从算法的时间复杂度、空间复杂度、数据结构形式以及实现的难易程度等方面分析了几种求关键路径算法的优劣.表明三种算法的时间复杂度分别为:O(n+e),O(n^2),O(n+e^2/n).  相似文献   

4.
研究了工件加工时间相同的确定单机调度最优交贷期和最优加工顺序的问题,且目标函数基于交货期和工件交货时间不准的情况。利用HLP不等式提出了时间复杂度为O(n^2)的最优算法。  相似文献   

5.
平面多轮廓加工路径优化模型及其近似算法   总被引:6,自引:0,他引:6  
应用一种节点可变的广义旅行商问题,为平面多轮廓加工路径优化问题建模.针对在分层实体制造中,轮廓加工路径的优化必须实时进行、优化计算时间必须小于因路径缩短而节省的加工时间的要求,以及每层加工的轮廓数量通常少于10^2、每条轮廓的节点数可能为10^3的特点,提出一种先用时间复杂度为O(n^2)的最近邻算法,求轮廓原始起点集合的旅行商问题解,然后在O(n)时间内改变每条轮廓的起点,进一步缩短路径长度的2步优化近似算法,从而兼顾了轮廓加工特点和算法实时性的要求.实验统计表明,该算法对路径的优化程度比仅按传统旅行商问题处理时提高了10%以上,且运行时间不超过0.1s。  相似文献   

6.
孙兴春  何文斌 《科技信息》2009,(20):202-203
本文分析了Douglas—Peucker(DP)算法的复杂度,表明在最坏情况下为O(n^2)其中n为矢量压缩前的顶点数。接着,提出了一种基于路径凸壳的算法,在最坏情况下的复杂度仍为O(nlog2),与常规DP算法在最优情况下的复杂度相同。  相似文献   

7.
基于可辨矩阵的属性约简算法都是从信息系统中直接求得约简,提出了分两步求得约简,降低了算法的时间复杂度为O(mn^2),第一步计算出近似约简,第二步去掉其中的冗余属性。改变了过去人们认为基于可辨矩阵的特征选择算法的时间复杂度不低于O(m^2n^2)的观点(其中m为数据集中特征/属性的个数,n为数据集中样本的个数)。最后给出了实验结果.  相似文献   

8.
本对P*(k)阵线性互补问题,给出了一种内点幂级数算法,其迭代复杂度为O(2k 1)^2n^(1 1/r)/2L^(1 1)/r,r为阶数。  相似文献   

9.
给出两种在SIMD-EREW计算模型上的最优并行排序算法,为了避免存储访问冲突,算法采用了基于并行归并的并行排序方法。对于长度为n的序列,在n^ε个处理单元上,算法的排序时间为O(n^1-εlbn),成本为O(nlbn),已达到了最优,且算法是自适应的。  相似文献   

10.
刘辉 《科学技术与工程》2007,7(13):3279-3282
研究了一维装箱问题的在线近似算法,给出了一种新的半在线算法:随机适应算法(简称RF算法),说明了RF算法的时间复杂度是O(n^2),一般情况下的性能比〈1.75。  相似文献   

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

12.
在滤波器设计中,特别是实时信号处理场合,有时对滤波器的性能要求并不高,但对处理速度要求高.这时,简单整系数滤波器就是理想的选择,而快速判定所设计的整系数滤波器是否稳定,则是至关重要的.给出一个快速算法来判定整系数滤波器的稳定性.该算法的复杂性为O(n^2),其中n为模拟滤波器传输函数分母多项式的次数.  相似文献   

13.
提出计算多面体面上任意两点之间最短路径的算法:近似算法、最短路径或近似最短路径算法.近似算法的思想是采用将折线不断嵌入三角形串上的方法,而另2个算法则是通过特定法线寻找三角形串,而且将这些三角形旋转到同一平面上,从而得到最短路径.前者的时间复杂性为O(n),而后者的时间复杂性分别是O(n2)及低于O(2nn2).  相似文献   

14.
采用文献[11]求解子串前缀的方法,给出了BM算法一个改进算法。改进算法最坏情况下的时间复杂度达到O(m*n/k),有效地减少了字符重复比较的次数,提高了匹配效率。  相似文献   

15.
本文提出求解带状 Toeplitz 线性方程组的一种新方法.其计算复杂度为O(n(p+q)),而不是一般 Toeplitz 方程组的算法的 O(n~2).这里,n 是方程的阶,p 和 q 分别是上和下半带宽.此外,该方法比用一般的带状 LU 分解方法既节省运算量,也少用计算机存贮.  相似文献   

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

17.
本文简述了从硬件描述语言到自动生成逻辑电路图的方法和步骤。在提出了与文献所不同的数学模型的基础上,设计了一种新的自动布局算法。该算法的时间复杂性在一般情况下远小于O(p·n~2)(p为元件列数,n为所有列中最大元件数),并且使连线总长及交叉点个数同时得到改善。本文的结果已在同期研制的逻辑/电路图编辑与自动生成系统中得到应用。  相似文献   

18.
针对近邻法分类需要大量计算和存储的缺点,提出了一种改进的样本挑选算法(different itera-tive case filtering,DICF).该算法首先评价每个样本的分类能力,据此不断删除分类能力弱的样本,迭代执行此过程,直到压缩子集不再变小为止.经分析得出DICF算法时间复杂度为O(n2).在真实数据库上的实验结果表明,通过DICF算法得到的压缩集在压缩比、分类精度上均优于MCS,ICF,ENN等经典算法.  相似文献   

19.
扩展了现有的基于O-Tree的布图算法,提出了一种可以处理带障碍模块的布图算法.修改了原算法中对O-tree的扰动(perturbing)方法,扩展了算法在布图解空间中的搜索范围.修改后的算法对自由模块进行布图,并通过消除自由模块与障碍之间的重叠,得到满足障碍位置约束的布图;其时间复杂度为O(n7/2m),其中n是自由模块的数目,m是障碍的数目.布图测试电路的运行结果显示,修改后的算法比原算法可以得到更优化的布图结果.  相似文献   

20.
单车独占性带时间窗口装卸货问题的分析与算法   总被引:2,自引:0,他引:2  
提出了一类广泛存在于运输领域的NP-hard组合优化问题——独占性带时间窗口装卸货(E-PDPTW)问题,给出了它的数学描述,分析了其性质并把问题简化为不对称带时间窗口旅行商问题(TSP),提出了求解单车E-PDPTW问题的两阶段快速算法,其时间复杂度只有O(n^3),测试结果表明了该算法的有效性和快速性。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号