共查询到20条相似文献,搜索用时 265 毫秒
1.
区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(logdn),综合性能为O((logn)2d)(使用CqCu模型)或O(K(logn)d)(使用Cqnq+Cunu模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构. 相似文献
2.
3.
4.
分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n2)处理器,时间复杂度为O(log2n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n3)处理器,计算时间复杂度为O(logn). 相似文献
5.
一种时间复杂度最优的精确串匹配算法 总被引:12,自引:2,他引:12
现有的串匹配算法通常以模式长度作为滑动窗口大小.在窗口移动后,往往会丢弃掉一些已扫描正文的信息.提出了LDM(linear DAWG matching)串匹配算法,该算法将正文分为[n/m]个相互重叠、大小为2m-1的扫描窗口.在每个扫描窗口内,算法批量地尝试m个可能位置,首先使用反向后缀自动机从窗口中间位置向前扫描模式前缀;若成功,则再使用正向有限状态自动机从中间位置向后扫描剩余的模式后缀.分析证明,LDM算法的最差、最好、平均时间复杂度分别达到了理论最好结果:O(n),O(n/m),O(n(1ogσm)/m).实际性能测试也验证了平均时间复杂度最优这一理论结果.而且,对于在较大字母表下查找短模式的情况,LDM算法速度在被测试算法中最快.总之,LDM算法不但适合进行离线模式匹配,而且还特别适合需要进行在线高速匹配的应用. 相似文献
6.
个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2kn2m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k1-1)k222h+(k1+1)2h+nk2+mk1)的新算法,其中,k1为一个片断覆盖的最大SNP位点数(不大于n),k2为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k2).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值. 相似文献
7.
8.
9.
有中断时间代价的一致并行机抢先调度问题 总被引:1,自引:0,他引:1
提出了一种具有中断时间代价的抢先调度问题(P|ptmn(δ)|Cmax):在抢先调度中,一个任务发生一次中断,其总的执行时间会增加一个δ.该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.证明了这是一个NP-hard问题,给出了一个时间复杂度为O(nlogn+m)的脱线近似算法LPT-Wrap,其近似比小于等于1.40825,并分析了P|ptmn(δ)|Cmax的在线特性,给出一个线性时间复杂度的在线近似算法,其竞争比为2. 相似文献
10.
11.
12.
算法复杂性平滑分析的研究进展与展望 总被引:2,自引:0,他引:2
有很多算法其最坏情况复杂性很坏(甚至是指数阶的), 但在实际应用中却很有效. 其中一个典型代表就是求解线性规划问题的单纯形算法. 最近, Spielman和Teng提出了算法的平滑复杂性概念及算法复杂性平滑分析方法, 对上述矛盾给出了合理的解释, 在理论计算机科学界引起了极大的关注.为此,做了以下工作:介绍算法复杂性平滑分析的基本概念;介绍两年多来算法复杂性平滑分析主要的研究进展; 从实际应用出发提出一个更合乎算法复杂性平滑分析思想的随机扰动模型(简称TSSP模型),克服“Partial Permutation”随机扰动模型的不足, 并证明在TSSP模型下快速排序算法的时间平滑复杂性为O(2/λn×log\\-2(n)), 其中λ是随机扰动幅度大小.最后,对算法复杂性平滑分析的研究提出了展望. 相似文献
13.
Wing-Kai Hon Tak-Wah Lam Kunihiko Sadakane Wing-Kin Sung Siu-Ming Yiu 《Algorithmica》2007,48(1):23-36
With the first human DNA being decoded into a sequence of about 2.8 billion characters, much biological research has been
centered on analyzing this sequence. Theoretically speaking, it is now feasible to accommodate an index for human DNA in the
main memory so that any pattern can be located efficiently. This is due to the recent breakthrough on compressed suffix arrays,
which reduces the space requirement from O(n log n) bits to O(n) bits. However, constructing compressed suffix arrays is still
not an easy task because we still have to compute suffix arrays first and need a working memory of O(n log n) bits (i.e.,
more than 13 gigabytes for human DNA). This paper initiates the study of constructing compressed suffix arrays directly from
the text. The main contribution is a construction algorithm that uses only O(n) bits of working memory, and the time complexity
is O(n log n). Our construction algorithm is also time and space efficient for texts with large alphabets such as Chinese
or Japanese. Precisely, when the alphabet size is |Σ|, the working space is O(n log |Σ|) bits, and the time complexity remains
O(n log n), which is independent of |Σ|. 相似文献
14.
A matrix A of size m×n containing items from a totally ordered universe is termed monotone if, for every i, j, 1⩽i2. In case m=nϵ for some constant ϵ, (0<ϵ⩽1), our algorithm runs in O(log log n) time 相似文献
15.
节点导纳矩阵是一个稀疏矩阵,短路电流计算需要对导纳矩阵数据进行查询。为了既能保持快速按行列查询元素数值,又进一步提高按数值查询其所在行列的效率,以便于存储调用及后续矩阵的处理,提出构建高度平衡二叉树的改进十字链表方法,即在十字链表存储的基础上,拓展存储数据结点指针域,形成平衡二叉树,将高度维持在(O(log2n)),平均查找长度也可维持在(O(log2n)),大大降低操作时间复杂度,提高数值查询效率。同时,为保证测试结果的公平性,把构建高度平衡二叉树的时间计入总时间,以进行对比。通过相应算例,验证了该改进方法的高效性。 相似文献
16.
QuickHeapsort is a combination of Quicksort and Heapsort. We show that the expected number of comparisons for QuickHeapsort is always better than for Quicksort if a usual median-of-constant strategy is used for choosing pivot elements. In order to obtain the result we present a new analysis for QuickHeapsort splitting it into the analysis of the partition-phases and the analysis of the heap-phases. This enables us to consider samples of non-constant size for the pivot selection and leads to better theoretical bounds for the algorithm. Furthermore, we introduce some modifications of QuickHeapsort. We show that for every input the expected number of comparisons is at most \(n\log _{2}n - 0.03n + o(n)\) for the in-place variant. If we allow n extra bits, then we can lower the bound to \( n\log _{2} n -0.997 n+ o (n)\). Thus, spending n extra bits we can save more that 0.96n comparisons if n is large enough. Both estimates improve the previously known results. Moreover, our non-in-place variant does essentially use the same number of comparisons as index based Heapsort variants and Relaxed-Weak-Heapsort which use \( n\log _{2}n -0.9 n+ o (n)\) comparisons in the worst case. However, index based Heapsort variants and Relaxed-Weak-Heapsort require \({\Theta }(n\log n)\) extra bits whereas we need n bits only. Our theoretical results are upper bounds and valid for every input. Our computer experiments show that the gap between our bounds and the actual values on random inputs is small. Moreover, the computer experiments establish QuickHeapsort as competitive with Quicksort in terms of running time. 相似文献
17.
针对压缩传感中高维投影计算采用稀疏性较差的普通随机测量矩阵,从而导致计算复杂度高,重构性能不佳这一难题,提出一种基于二分图邻接矩阵的压缩传感图像快速重建算法。该算法在满足测量矩阵的RIP条件下,充分利用二分图邻接矩阵的稀疏性与二值性,将时间复杂度由传统算法的O(N·logN)降低至O(N)。实验结果表明,算法在保证图像重构质量情况下大大提高了运算性能,尤其对于色彩(灰度)变化平缓图像,该算法性能更加优越。 相似文献
18.
基于广义图像灰度共生矩阵的图像检索方法 总被引:9,自引:0,他引:9
当图像发生旋转或大小改变显著时,用已有的基于灰度共生矩阵的图像检索方法,不能很好地给出检索结果,在此基础上,该文提出一种基于广义图像灰度共生矩阵的图像检索方法。该方法将原图像作平滑处理得到平滑图像,然后将原图像和平滑图像组合起来得到广义图像灰度共生矩阵,提取该矩阵的统计特征量后,将其组成向量并归一化后用于检索。该方法引入了图像的空间信息,对于图像旋转和尺寸变化均不敏感。实验结果与性能比较表明,新方法的效果优于单纯的灰度共生矩阵法。 相似文献
19.
现有的均匀交换结构只能单独支持速率保证业务或单独支持尽力而为业务.本文研究如何利用均匀交换结构实现对多类型业务同时支持问题.提出采用速率分配和改变缓存队列组织结构的方法实现多类型业务的支持;针对该方法所产生的交叉节点缓存最大占用增大问题,提出两级均匀调度策略,并进一步对均匀速率调度算法做出改进,降低存储复杂度.通过理论分析和仿真实验证明了在支持多类型业务的情况下均匀交换结构的复杂度没有提升. 相似文献
20.
求解正则式方程式集合的面向矩阵高斯主元消去法 总被引:1,自引:0,他引:1
张伟 《计算机研究与发展》1995,32(12):50-55
本文在论述利用系数矩阵进行消元变换求解正则表达式方程式集合的高斯消去法的基础上,提出了一种选取系数矩阵中主元素进行消元变换求解正则表达式方程式集合的高斯主元素消去法,并给出易编程的算法。 相似文献