共查询到10条相似文献,搜索用时 46 毫秒
1.
一种基于数据块交换的快速稳定原地归并算法 总被引:1,自引:0,他引:1
与其它排序算法相比.二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个
有序子表,经典算法有2种/第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动/第
二种算法是原地的.但完成归并需要O(m+n)次比较和O(m*n)次移动,提出了一种基于块交换的快速
稳定原地二路归并算法.实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数. 相似文献
2.
一种基于数据块交换的快速稳定原地归并算法 总被引:2,自引:0,他引:2
与其它排序算法相比,二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个有序子表,经典算法有2种。第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动。第二种算法是原地的,但完成归并需要O(m+n)次比较和O(m×n)次移动。提出了一种基于块交换的快速稳定原地二路归并算法。实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数。 相似文献
3.
为改进直接选择排序算法的不稳定性及对数据的不敏感性,笔者研究了表选择排序算法.该算法约定用静态链表存储待排数据,先创建有序链表,再根据链接信息将数据顺序存储.此算法不仅保证排序算法的稳定性,也使时间复杂性由原来的O(n~2/2)在最好和平均情况下分别降到O(n)和O(n~2/4)(最坏情况不变),另外还保证后续其他操作也同样具备顺序存储的优点.从排序稳定性、数据比较次数和移动次数三方面来看,本文中提出的排序算法在简单排序算法中是最优的. 相似文献
4.
周玉林 《上饶师范学院学报》2004,24(6):73-75
本文讨论了有限期作业调度问题,用计数排序、分离森林中的有效路径压缩、按秩合并方法,得到了有限期作业调度最优化算法,其时间复杂性为O(na(m,n)),m=O(n),在实际应用中是一个线性时间复杂性算法,是渐近性能最佳的算法. 相似文献
5.
沈光星 《杭州师范学院学报(自然科学版)》2003,2(4):1-4
利用快速傅立叶变换 (FFT) ,给出了 n阶循环矩阵开平方的一个快速算法 ,计算循环矩阵的同型平方根矩阵 (平方根矩阵也是循环矩阵 ) ,证明了同型平方根矩阵的个数为 2 n ,它是关于 n的指数函数 ;计算一个同型平方根矩阵的时间复杂性为 O(nlog2 n) ;计算全部同型平方根矩阵的时间复杂性为 O(n2 n) . 相似文献
6.
批处理机上有就绪和截止时间的等长度工件排序 总被引:1,自引:1,他引:0
刘朝晖 《重庆师范大学学报(自然科学版)》2009,26(3):1-004
一台批处理机一次可以同时加工多个工件(称为一批),每批工件有相同的开工和完工时间,加工时间等于其中最长工件的加工时间.本文研究单台批处理机上有就绪时间和截止时间约束的n个等长度工件的排序问题,目标是求一个可行时间表.就该问题,Baptiste已经提出了一个复杂性为O(n8)的算法,在此基础上,本文推广Garey等人关于对应的经典排序问题的算法,得到了一个复杂性为O(n2)的算法.算法分两个阶段执行:在阶级I,算法找出所谓的禁止开工区间,在这些区间中将不允许有工件开工;在阶段II,算法从时刻零开始,每当机器有空闲且不属于禁止开工区间的时候,就按照最早截止时间优先规则从已就绪的未加工工件中选择尽可能多的工件作为一批进行加工,若当前的机器空闲时刻属于某个禁止开工区间,则首先更新其到该禁止开工区间的右端点再进行决策. 相似文献
7.
单机分族分批排序的最小误工个数问题 总被引:1,自引:0,他引:1
曹国梅 《四川理工学院学报(自然科学版)》2008,21(5)
文章研究了同一族内,给出并证明了其最优排序的性质。对工件到达时间和工期相一致时的情形,得出了一个时间复杂性为O(mb(n/m)2m)的动态规划算法。 相似文献
8.
9.
通过分析任意输入的n个数据的组成特性,设计一种O(n nlog2m)时间复杂度的排序算法,m为原始输入数据序列中有序/逆有序的子序列个数,1≤m≤n/2。此排序算法的时间复杂性结果与输入数据的概率分布假设无关。 相似文献
10.
一个基于桶技术的平面点集Voronoi图增量算法 总被引:1,自引:0,他引:1
设计并实现了一个有效的平面Voronoi图增量算法 .该算法以翼边数据结构为基础 ,应用桶技术选择生成子并提高近邻搜索效率 ,可处理平面点集三点共线、四点共圆等退化情形 ,并具有较高的计算精度 .尽管理论上算法的最坏时间复杂性为O(n2 ) ,实验结果表明算法的平均时间复杂性近似为O(n) . 相似文献