共查询到19条相似文献,搜索用时 171 毫秒
1.
现有的排序算法很难实现自定义顺序的字符串排序,提出一种自定义顺序的字符串快速排序方法.在应用连续编号定义字符排序顺序的基础上,使用哈希表结构将字符串转换成对应的整型数组,以字符的最大编号作为基数排序算法的新基数,实现字符串的基数排序.分析和实验表明,本文方法可有效实现自定义顺序的字符串排序,是一个时间和空间复杂度都是线性的排序算法,比快速排序(Quick Sort)具有更好的时间性能,且可以方便地推广到其它语言的字串排序中. 相似文献
2.
目前,基于基数排序的等价类划分算法有较低的时间复杂度但存在以下不足:属性值跳跃性大时会产生大量空队列;排序后仍需O(|P‖U|)的时间才实现划分,求出等价类,排序没能发挥应有作用。为此,设计了一种新算法,通过属性值映射避免大量空队列产生,通过增加一个记录等价类长度信息的计数数组,排序后仅需O(|U|)就可实现划分,求出等价类。整个算法时间复杂度为O(|C‖U|),空间复杂度为O(|U|),为求等价类划分提供了一个新的解决办法。 相似文献
3.
通过构造对称分块矩阵给出了秩为m的m×n阶Toeplitz型矩阵Moore-Penrose逆的快速算法。该算法计算复杂度为O(mn)+O(m2),而由TT(TTT)-1直接求解所需运算量为O(m2n)+O(m3)。数值算例表明了该快速算法的有效性。 相似文献
4.
现实应用中,计算机处理的数据往往是非精确的。对于非精确的输入数据,一般使用线段,圆和正方形等模型表示。对以平行线段代表非精确数据的模型研究非常重要,因为这种非精确数据模型是解决其他更复杂模型的基础[1]。loffler等[1]给出了一种算法,可以在时间O(n3)内求出以竖直平行线段表示的非精确数据的最大面积凸包。但是该算法对于任何输入数据计算量都是一样,而现实生活中的非精确数据往往不是完全没有规律的,比如来自同一设备采样的数据的误差范围是一致的。首先给出了一种新的算法,可以在O(nlog(n))时间内求出具有相同取值范围的非精确数据的最大面积凸包,同时研究了输入数据是n个非精确数据和m个退化为精确数据的非精确数据如何求最大面积凸包的问题。如果把这些已经退化的非精确数据仍然看作非精确数据,套用文献[1]的算法时间复杂度将会是O((n+m)3)。针对这种情况给出了一种算法,算法时间复杂度为O(n3+nm)。 相似文献
5.
6.
7.
目前,基于不完备决策表的属性约简研究较少。基于信息量的不完备决策表属性约简是一种新的属性约简。由于在该属性约简中,计算相容关系是最主要的计算,也比计算等价关系要难得多。基于信息量的不完备决策表的属性约简算法的时间复杂度一般为O(|C|2|U|2)。为降低其时间复杂度,首先分析了老算法的不足,然后给出了一个效率较好的计算相容类的算法。最后设计了一个新的基于信息量的不完备决策表的属性约简算法,其时间复杂度为O(|C|2|U|2)。 相似文献
8.
该文考虑网络数据更新,需要控制代理服务器与客户的距离时,网络中的代理服务器的放置问题。找到代理服务器的最优数量和放置位置,使网络中数据访问的总花费(包括数据读取和更新)最小。利用二叉树结构和动态规划方法,得到了一个时间复杂度O(n2)的多项式时间算法,其中n为网络结点数。 相似文献
9.
钟雪灵 《计算机工程与应用》2010,46(7):229-231
研究了在给定截止期限(deadline)下的单机分批(batch)排序问题,目标函数是最大提前完工时间。由于工件不能延迟,因此先讨论了问题可行解的存在。当问题有可行解时,证明了工件按最早截止期限(Earliest Deadline,ED)规则的排序是一个最优排序,接着给出一个时间复杂度为O(n3)的动态规划算法来获得最优分批。 相似文献
10.
考虑到在实际应用中,由于计算机和通信网络中一般每个设备的处理能力是有限的,在k-tree core问题的基础上,提出了同时带有度约束的k-tree core问题,即k-tree core中的每个节点在子树中的度不超过给定常数q,记为q-DTC(k)(Degree constrained Tree Core)。利用动态规划的方法,采用最优化原则先找出文中所定义的局部根核集,然后利用贪婪思想对不满足度限制的节点所在的分支加以删减,对无权树和赋权树得到了复杂度分别为O(kn)和O(max{n log n,kn})多项式时间算法,其中n是树的节点数。 相似文献
11.
关于求核的算法有很多,本研究利用选择排序的思想设计了求解等价类的算法,其时间复杂度为O(|C||U|)。在此基础上,设计的求核算法,算法时间复杂度为O(|C|^(2)|U|)。通过实验,证明了算法的正确性和高效性。 相似文献
12.
分析了不同测试项目对于一款采用0.18μm工艺流片的高性能通用处理器芯片失效的发现能力.以失效分析的数据作为基本数据结构,提出了测试项目有效性和测试项目耗费时间的折中作为启发式信息的优化算法,利用该算法生成的测试流程可以减少失效芯片的测试时间.该算法和动态规划算法相比,计算复杂度从O(dn^2n)降低到O(dn^3).最后用实验数据证明了该算法的有效性. 相似文献
13.
An algorithm for the computation of the edit distance of run-length coded strings is given. In run-length coding, not all individual symbols in a string are explicitly listed. Instead, one run of identical consecutive symbols is coded by giving one representative symbol together with its multiplicity. The algorithm determines the minimum cost sequence of edit operations transforming one string into another. In the worst case, the algorithm has a time complexity ofO(n·m), wheren andm give the lengths of the strings to be compared. In the best case, the time complexity isO(k·l), wherek andl are the numbers of runs of identical symbols in the two strings under comparison. 相似文献
14.
15.
基于数组的桶排序算法 总被引:1,自引:0,他引:1
经典桶排序算法以链表形式实现"桶",处理均匀数据效率很高,是O(N)算法 .但对极不均匀数据则退化成低效的O(N2)插入排序 .讨论了记录携带附加数据的计数排序算法,将"桶"实现为顺序数组,避免链表的动态内存分配直接提高算法效率,并允许快排等O(N log N)算法处理桶内数据 .对均匀数据仍然保持O(N)时间复杂度,对极端不均匀数据则只退化为O(N log N)的原算法 .对一般非均匀数据,证明数组桶排序算法总体性能高于经典算法 .均匀数据实验表明,桶排序算法明显优于Linux下标准qsort系统调用,且数组桶排序算法效率更高 .而在非均匀的正态数据实验中数组桶算法性能下降明显小于经典桶排序,总体效率仍然优于qsort的直接应用 . 相似文献
16.
KLT算法已在多个领域得到成功的应用,其中特征点的排序是用来选择好的特征点跟踪的关键。针对传统排序算法计算耗时、实时性差的缺点,提出一种可并行的多层次归并排序算法并在FPGA中实现了其并行计算,同时分析了其周期精确的计算时间。结果表明该归并排序算法可以[O(N)]的时间复杂度完成特征点的排序,能够满足高清分辨率的图像/视频数据中KLT特征点排序的实时性要求。 相似文献
17.
18.
基于存储结构的汉字分组排序及其复杂度分析 总被引:1,自引:0,他引:1
自从计算机被用来进行大规模的数据处理,数据序列的排序问题便一直成为研究的热点,汉语言本身所具有的特点,使得汉字符串的排序问题成为中文信息处理领域中备受关注的问题,提出了一种汉字符串的快速分组排序算法,算法复杂度仅为O(n)。 相似文献
19.
用动态规划算法求解0-1背包问题的时空复杂度为O(nC)。这个空间复杂度在求解大规模问题上是不可接受的。从计算0-1背包问题最优值的递归方程出发,给出高效利用内存的动态规划算法。为了克服内存高效的动态规划算法带来的缺点,设计新混合算法求解0-1背包问题。该新混合算法的时间复杂度为O(nC);它消除了回溯阶段,并且为求得放入背包的物品所使用的空间复杂度仅为O(「n/d?+C),其中d为计算机字长。实验结果表明,混合算法的工作效率与理论分析相同。 相似文献