分块递归序列比对算法

利用分块递归的思想,结合检查点计算方法,提出一种线性空间复杂度序列比对算法,对于给定长为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%以上.     

Cauchy矩阵Moore-Penrose逆的快速算法

给出了求以秩为n的m×n阶Cauchy矩阵Moore-Penrose逆的快速算法,该算法的计算复杂度为O(mn)+O(n2)。而用C+=(CTC)-1CT求解C+时所需的运算量为O(mn2)+O(n3)     

经典启发式量子计算整数分解问题

大整数分解是破解RSA加密算法的基本途径之一，由于计算量过大，经典计算机难以有效解决大整数分解问题.量子叠加和纠缠的特性，使得量子计算可以对经典问题求解起到并行加速的作用. Shor算法是一个能够高效快速对大整数分解的量子算法.然而，Shor算法需要进行模幂运算，使得电路设计极其复杂，时间复杂度也高.为了解决该问题，基于经典计算的启发，提出一种启发式算法：利用量子计算的并行性，设计相关Oracle去计算2个奇数叠加态a和b的乘积，再将叠加态乘积的负相位加在大整数N的傅里叶基上，当结果为0时，利用多控制门便能够将满足pq=N的一个质因子p给提取出来.该文提出的算法最低仅需要2n个量子比特，时间复杂度也达到指数级加速.另外，该文在QISKit框架上实现了该算法，证明了算法的可行性和通用性.     

一种基于TCAM的PLO_OPT算法的改进

在最大前缀长度为L的TCAM(Ternary Content Addressable Memory)中,采用PLO_OPT算法更新路由表项仍然有很大的时间消耗,其时间复杂度为O(L/2)。为了进一步提高路由更新速度,根据路由前缀数量分布图,本文提出了一种PLO_OPT路由更新算法的改进方案,每更新一次表项只需进行一次操作即可,可以使时间复杂度达到O(1),且更有效地利用了存储空间。     

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

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

改进的快速排序算法

本文通过分析快速排序算法中固有的不足之处,提出了改进的快速排序算法,并对算法的时间复杂度进行分析,通过编写程序上机实验,将原算法与改进的算法运行所需时间进行比较,证明了改进算法的有效性。     

RA码译码简化算法的研究

RA码BP译码算法，可以实现线性时间译码，然而具有较高的复杂度。为了便于硬件实现，首先提出将最小和算法应用于RA码，然后对最小和算法进行了改进，提出了归一化算法和偏移算法，使循环译码算法在复杂度和性能之间取得了较好的折衷。仿真结果表明：归一化算法和偏移算法复杂度低，性能接近BP算法。     

求解最小支配集的线性混合整型规划算法

提出了一个高效的求解最小支配集问题的线性混合整数规划算法(MILP).该算法主要针对最小支配集问题的特点建立整数规划模型,并通过Gurobi求解器进行优化求解.采用当前国际文献公开的共74个算例作为算法测试实验集,与FKW算法、传统的Grandoni算法以及改进的Grandoni算法进行比较.实验结果表明,该算法的计算效率明显优于其它的精确算法,且在所有算例上都能得到精确解.     

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

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

基于聚类和分段优化的蚁群算法

针对蚁群算法在求解大规模旅行商问题(TSP)时精度和时间方面的不足,提出了一种新的算法,该算法采用多阶段的蚁群寻优策略.算法的复杂度分析及在大规模TSP问题上的实验表明:该算法在保证获得较好解的前提下收敛速度得到了较大的改进.     

确定周期为pn的q元序列k-错复杂度曲线的一个快速算法

k-错复杂度是指改变序列一个周期段中k个或少于k个符号后所得到的序列的最小线性复杂度,k-错复杂度曲线即为该序列的k-错复杂度序列,该指标完全反映了当序列改变的比特数目不断增加时线性复杂度的变化情况．文中给出了一个确定周期为pⁿ的q元周期序列k-错复杂度曲线的算法,这里p,q为奇素数,并且q是模p的一个本原根．该算法分别推广了肖-魏-林等人计算q元pⁿ周期序列线性复杂度和魏-董-肖计算q元pⁿ周期序列k-错复杂度的算法．采用文中的算法计算q元pⁿ周期序列的k-错复杂度曲线至多需要Θ(2ⁿ⁺¹)步运算.     

数据挖掘技术中聚类算法的改进研究

针对K-means算法所存在的问题进行了深入的研究,提出了基于密度和聚类对象方向的改进算法(KADD算法).该算法采取聚类对象分布密度方法来确定初始聚类中心,然后根据对象的聚类方向来发现任意形状的簇.理论分析与实验结果表明,改进算法在不改变时间、空间复杂度的情况下能取得更好的聚类结果.     

G.729语音编码算法优化研究及ARM实现

基于ARM(advanced RISC machine)体系架构和嵌入式Linux操作系统构建了算法平台,并在该平台上移植了G.729语音编解码算法.为了降低G.729算法的复杂度,提出了一种基于部分失真搜索(partial distortion search,PDS)和范数排序搜索(norm order search,NOS)的LSP(line spectrum pair)矢量量化算法及基于ARM指令集的算法优化策略.实验结果表明:改进后的G.729算法和ARM实现方案大大降低了语音处理时间,极好地满足了点对多点实时语音通信的要求.     

基于密度进化的低密度校验码的最小和量化译码器的算法设计

低密度校验码量化译码器的设计对低密度校验码的实用化有重要意义.本文根据密度进化理论,对规则/非规则的低密度校验码提出了一种算法,该算法能优化最小和均匀/非均匀量化译码器的设计.与连续和积译码器相比,用此算法设计的最小和量化译码器虽然性能稍有损失,但是译码器中的运算仅涉及整数加法运算,极大地降低了计算复杂度.     

基于改进差别矩阵的增量式属性约简算法

研究目前粗糙集中求属性核和属性约简存在的效率低下问题,提出基于改进差别矩阵的核增量式更新算法,用于解决对象动态增加情况下核的更新问题.为降低现有增量式属性约简算法的时间和空间复杂度,提出一种不存储差别矩阵的高效属性约简算法,用于处理对象动态增加情况下属性约简的更新问题.理论及实验结果表明,该算法可明显降低时间和空间的复杂度.     

基于右移k ary消减的递归最大公因子算法

对于输入B和C,利用Sorenson的右移k ary消减（right shift k ary reduction）思想提出一种算法用于寻找整数x和y,使得x和y满足Bx－Cy在二进制表示下低比特位部分为0,利用该算法能够大规模降低循环次数,再结合模算法,提出递归最大公因子算法。递归最大公因子算法复杂度虽然对Knuth Schnhage算法的复杂度上没有提高,仍然是O(nlog2nloglogn),但是该算法相比于Knuth Schnhage算法实现简单,正确性分析和复杂度分析都比较容易。     

改进光流算法在地震图像纹理分析的应用研究

为在消除噪声的同时有效保护地震图像线性结构,提出一种改进光流算法与纹理平滑滤波相结合的新方法.首先,利用高斯金字塔多尺度描述方法解决大流速计算问题,提高精度;其次通过设置迭代结果残差的均方根的门限值,减少迭代次数,缩短处理时间;最后,根据地震图像剖面纹理复杂度,结合纹理属性分析,选用不同的模板进行纹理平滑滤波,提高信噪比.经与传统的均值滤波和目前较先进的改进Sobel滤波器以及利用标准化全梯度进行地震图像边界探测的方法相比,本文提出的算法能够有效的保存地震数据的边缘信息,增强地震图像同相轴的连续性,提高信噪比7～10 dB,缩短处理时间2～3分钟.实验结果表明:本文构建的高斯金字塔多尺度描述与光流算法结合,同时结合纹理平滑滤波构成的综合改进算法,在提高信噪比的同时,较好地保持了原图像的纹理结构和能量,并减少了处理时间,提高了地震资料解释的效率,是目前地震图像纹理分析领域处理效果较好的方法之一.     

一种基于搜索空间分解的报文分类算法

报文分类算法的关键问题是查找准确且快速,最简单的分类算法就是线性查找,该算法的时间复杂度和空间复杂度均为O(N),线性查找的思想简单、易于实现、空间复杂度好,可以和其它算法混合使用,进而提高算法的分类速度。快速的分类算法采用很复杂的数据结构,牺牲空间来换取时间,甚至过分要求分类的快速性,忽略了空间性。文章根据这一问题进行展开,详细分析了经典的报文分类hicuts算法,分析其时间复杂度和空间复杂度的关系,并提出一种不过分降低分类速度的前提下,有效降低空间复杂度和预处理时间的改进方法。     

基于粗糙集改进的KNN级联均衡器抑制LED非线性研究

针对LED非线性响应导致可见光通信性能严重下降的问题，提出基于粗糙集理论改进的k最近邻(KNN)算法，并与最小均方(LMS)算法相结合，设计了级联均衡器。首先，根据接收端星座点分布特征，将训练集数据空间划分为不同的区域，并对不同区域采用不同的分类策略，从而降低了传统KNN算法的计算复杂度；然后，提出将LMS均衡器与改进的KNN均衡器相结合。第1级LMS均衡器有助于降低样本点的弥散度，为提高第2级改进KNN均衡器的分类准确性和减小计算复杂度提供了条件；最后，采用蒙特卡罗方法对系统进行了仿真实验。实验结果表明，改进KNN算法的复杂度约为传统KNN算法的1/9,且不会牺牲分类准确性。同时，使用所提的LMS算法和改进KNN级联均衡器能显著改善可见光通信系统的性能。     

一种基于网格查询的改进DBSCAN算法

针对DBSCAN算法聚类时时间复杂度较高、当边界点同时属于多个类时其聚类准确率较低的问题,在网格查询思想和OPTICS算法的基础上,提出一种改进的DBSCAN算法(GO-DBSCAN算法)。进行聚类操作前,为降低聚类的时间复杂度,先基于网格查询的思想将数据集划分成不同的网格,在进行项目邻域查询时,只须遍历项目附近网格数据而不必遍历整个数据集; 在进行项目聚类时,主要考虑该项目与其附近核心项目的最小可达距离,因此,将OPTICS算法中的最小可达距离引入到DBSCAN算法中,以提高算法对边界点处理的准确度。仿真实验结果表明,GO-DBSCAN在边界点处理的准确率和运行效率方面较DBSCAN都有所提高。