分块递归序列比对算法

利用分块递归的思想,结合检查点计算方法,提出一种线性空间复杂度序列比对算法,对于给定长为m和n的2条序列,空间需求约5(m+n)+Lsmin(m-1,n-1)+C2~5(m+n)+Ls(m+n-2)+C2,而时间需求一般情况下约1.5mn~3mn,在待比对序列相似度较高时约1.5mn~2mn,并通过同源物种全基因组序列比对实验证明,如果归一化编辑距离小于0.25,那么该算法比Hirschberg算法快10%以上.     

对称Loewner方程组极小范数最小二乘解的快速算法

对于工程计算中常常遇到的一类线性方程组的求解,通过构造特殊分块矩阵并研究其逆矩阵的三角分解,给出了求秩为n的m×n阶对称Loewner矩阵为系数阵的线性方程组,及极小范数最小二乘解的快速算法,该算法的计算复杂度为O(mn) O(n2),而一般方法的计算复杂度为O(mn2) O(n3).     

有限域上多项式分解的一种快速算法

本文给出了有限域上单变元多项式分解的一种概率算法。为了分解有限域Fq上一个次数n的多项式,该算法的时间开销为O(nω(1,3/4,3/4)+n1+o(1)logq)个Fq中算术运算。算法主要思想来源于Kaltofen＆Shoup的算法。     

新的DTDs一致性判断算法

DTD s(或Schem a)的一致性是XML研究中的一个新兴课题.小型的DTD s可以根据常识进行检查以保证其一致性,但对于大型的或者由其他数据模型(例如ER模型)转换的DTD s,则需要一种能够实现自动检测的机制.现已提出的DTD s一致性判断算法中,最坏时间复杂性为O(2mn)的S.Lu算法是较具代表性的一种.改进后的S.Lu算法提高了效率,最坏时间复杂性为O(n).     

基于快速自适应聚类算法的网络异常检测方法

随着Internet遍布到世界的各个角落,计算机暴露在互联网的各种恶意攻击前。我们需要行之有效的入侵检测系统来保护计算机免受这些恶意攻击的侵扰。现有基于信号的检测方法十分依赖加标识的训练数据,而对于新型的攻击束手无策。尽管基于聚类的检测方法可以克服这个缺陷,但是聚类方法的时间开销太大,从而导致网络管理员的反应延迟。本文介绍了一种新型的快速自适应聚类算法(FACA,FastAdaptive C lusterA lgorithm)该算法的时间复杂度为O(mn),n为数据点的数量,m为采样的次数,m的值远小于n,然而传统聚类方法的时间复杂度为O(n2),采用KDD CUP99的实验数据对该方法进行了评估,结果表明,相对于传统聚类方法,FACA显著的提高了检测效率。     

基于划分的基数交换排序算法改进研究

基于划分提出了一种改进的基数交换排序算法.改进后的算法只需少量额外内存即可将时间复杂度调整到Θ(mn),其中m为数据二进制的存储位数,而且除了处理整数外算法还能处理浮点数.针对提出的改进算法,本文还进行了优化,通过定理4论证,正(负)整数的时间复杂度降至Θ(nlog_2(ω)),其中ω=max⊕min表示序列最小值与最大值的位异或结果,引理1证明,算法时间复杂度降至Θ(min(mn,nlog_2n)).本文提出的改进算法能从时间以及空间上提升算法效率.     

三值光学计算机的多数位MSD乘法算法及运算分析

为探讨利用光计算二维并行处理信息特性以降低逻辑运算复杂度。文中采用三值光学计算机对MSD加法算法进行了改进,提出了三值光学计算机n位数的MSD乘法运算实现方法。通过算例对MSD乘法算法进行了时间性能分析以及MSD乘法三值光学加法器利用率分析.研究结果表明:三值光学计算机的MSD乘法算法可以完成两个n位MSD乘法,时间复杂度较传统乘法算法降低到O(log2n),三值光学加法器的利用率为((n/2-1)+(n/4-1)+…+1))/nlog2n.     

散列快速排序

多队列快速排序算法的平均时间小于已知的O(nlogn)快速排序算法。它的平均时间是O(nlogm),其中m∈(1,[n/2])。本文提出的算法对n个元素的排序时间为O(n)。在PC—88机上运行的结果符合文中给出的算法分析。     

线性划分问题的一个改进算法

给定一个由n个非负数构成的序列X={x1, x2, …, xn}及正整数k≤n, 线性划分问题要求将该序列划分为不大于k段子序列,使得最小化各段子序列元素之和为最大值。目前已知该问题的最好算法是时间复杂度为O(kn2)和空间复杂度为O(kn)的动态规划算法。利用非负数序列的性质,给出一个快速改进算法,其时间复杂度为O(knlogn),空间复杂度为O(n)。     

一个反对称矩阵乘法的快速算法

矩阵乘法是数值计算中的常见问题,其运算阶的降低一直是人们关注的基本问题,而多项式求值、多项式插值及多项式求导问题迄今已出现了许多有效且稳定的快速算法。讨论了一个n阶反对称矩阵与n维列向量的乘法问题,证明了该问题与多项式求值问题的等价性,提出了一个运算阶为O（n(log2n)2）的快速算法,并讨论了一个反对称矩阵乘法的例子,其O(n2)的运算阶在反对称矩阵乘法情形至少可降低到O（n(log2n)2）。     

一个基于分治法的快速多精度乘法

多精度运算中,乘法的设计与实现非常复杂,传统的多精度乘法的时间复杂度为O(n2),基于分治法介绍了一种改进的快速乘法,通过理论分析,改进算法的时间复杂度为O(nlog23).     

基于极值索引的数据排序算法

提出一种新的数据排序算法,将数学极值的求解原理与数据排序结合,把极小值的概念扩展到记录的序列中,并按数据的排列规律,建立了极小记录索引,通过索引快速搜索待排序列中的记录,对待排序列快速的排序。该算法的最大时间复杂度T(n)为O(nlogn)和空间复杂度O(n),在提高排序效率的同时,保证了排序结果中的相同大小记录之间相对位置的稳定。     

磁盘阵列Cache算法精确测评系统研究

磁盘阵列Cache算法的优劣是决定磁盘阵列性能的关键因素之一,精确的测试和评估方法对设计高效率的Cache算法至关重要.为了精确评估磁盘阵列中Cache算法的性能及其对系统I/O性能的影响,设计了一个Cache算法测评系统.依据磁盘阵列的系统构成和运行模式,建立了评估Cache算法的运行环境模型,包括I/O操作的产生和排队模块、Cache算法插槽模块、预取算法模块和磁盘模拟器4个部分.其中I/O操作的产生和排队模块能够产生多种形式的I/O操作负载及重放实际系统的I/O操作负载;Cache算法插槽模块用来挂载待评估的Cache算法;磁盘模拟器采用DiskSim,保证了测量磁盘I/O操作响应时间的精确性.系统能够精确测量Cache算法的命中率,以及对存储系统I/O操作平均响应时间的影响.实际测量了LRU算法的命中率和I/O操作平均响应时间,测量结果与既有的研究成果相吻合,从而验证了系统的性能.因此,系统具有良好的可靠性、可用性和可扩展性.     

周期三对角Toeplitz线性方程组的并行算法

提出一种求解一类周期三对角Toeplitz线性方程组的并行算法.此算法的计算复杂性为O（5n）,通讯复杂性为O（1）,并给出了误差分析.在 HP xr2600 集群上的试验结果表明其并行效率可达90%以上.     

最值吸收算法解决矩阵连乘次序问题

通过分析矩阵序列乘法的特点,找到了一种新的算法一最小维数边界吸收算法,并将此算法分别与穷举搜索算法、动态规划算法的时间复杂度及空间复杂度进行分析比较．可以看出,动态规划算法的时间复杂度为O（n^3）,空间复杂度为O（n^2）,而本算法的时间复杂度和空间复杂度均为O（n）,并且不需要额外的空间开销．     

Cluster-Based Distributed Algorithms for Very Large Linear Equations

LetAbe ann×nreal matrix,letBbe a vectorinRn,and consider the system of linear equationsAX=B,whereXis an unknown vector to be deter-mined[1].There are many solving methods such asserial software LINPACKetc.[2,3],usually classifiedas direct and iterative,direct methods find the exactsolution with a finite number of operations,typicallythe order isO(n3),iterative methods do not obtainan exact solutioninfinite ti me,but they converge toa solution asymptotically.In many applications suchas c…     

一个新的线性规划预校正算法

提出了一种新的线性规划预校正算法,预步是取的Ｅｕｌｅｒ方向,算法复杂度为Ｏ（n~(1/2)Ｌ）     

一种累积量线性预测方位估计的快速算法

提出了一种基于四阶累积量的线性预测方位估计快速算法。通过对累积量线性预测基本方法进行变换,得到了基本方程系数矩阵的Toeplitz结构,并用Levinson-Durbin算法求解方程,减少了运算量。在线性预测方程中,使用了四阶累积量,有效地抑制了高斯噪声。计算机仿真结果表明了这种方法的有效性。     

基于Jacobi迭代的大规模MIMO系统低复杂度软检测算法

基于Jacobi迭代提出一种低复杂度信号检测算法,在算法实现中避免了矩阵求逆运算.数学推导证明,该算法应用于MMSE检测时是收敛的,与传统的Neumann级数展开方法对比,能达到与其完全相同的检测性能,并且在任意迭代次数下能将复杂度保持在O(K2),而后者当级数展开项数大于等于3时复杂度上升为O(K3).为了进一步将Jacobi迭代应用到软判决中,提出了一种用于信道译码的LLR的近似计算方法.仿真结果表明,经过几次迭代,Jacobi迭代算法收敛较快,并接近MMSE检测性能.