ACELP语音编码算法改进与仿真

代数码激励线性预测算法（ACELP）是目前诸多低速率语音编码标准的算法核心,包括3G语音标准VSELP、AMR、AMR—NB、AMR—WB．该算法基于码激励线性预测模型,通过对码本的有效搜索,确定基音延迟,算法时间复杂度为O（n^3）．本文在ACELP算法基础上,对ACELP中自适应码本搜索过程进行改进,提出E—ACELP算法．通过AMR标准中8种速率情况的仿真,E—ACELP算法码本搜索时间减少、时间复杂度下降．基于E—ACELP算法,语音编码标准性能和效率得到提高．     

对称Toeplitz矩阵特征值的快速算法

利用n阶对称Toeplitz矩阵的结构特点和对称性,给出了计算该类矩阵所有特征值的一个快速算法,该算法的计算复杂度仅为O（n^2logn）。     

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

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

寻找平面上点的凸壳

对格雷厄姆算法进行了改进，编程实现寻找平面上n个点的凸壳，并通过1次循环就找出所有凸壳的顶点．该算法的空间复杂度为O（n-3），其时间复杂度在最坏情况下虽然无法突破O（nlogn）的理论下限，但在最好情况下已达到线性水平．     

最小生成树算法的快速实现

给出一种基于向量合并的最小生成树算法 ,它的时间复杂度和空间复杂度分别为O(E)和O(max(E ,V) ) ,算法简洁、快速     

利用矩阵搜索求所有最长公共子序列的算法

利用动态规划法求出二维数组的情况下,使用矩阵搜索的方法求出所有分支,从而求出所有最长公共子序列的算法．该算法将通常认为的指数量级的时间复杂度降低到了max{O（cmn）,O（ck）}．随后对此算法的正确性以及效率做了证明．     

利用堆排序优化路径搜索效率的分析

随着计算机技术的发展,路径搜索算法在许多领域内得到广泛的应用,对搜索时间要求提出更高的要求．为了解决这一问题采用基于人1二智能的启发式搜索算法,利用网络拓扑图给出的信息动态地调整搜索方向,并利用二叉堆进行算法优化,从而达到提高搜索效率的要求．常规使用启发式搜索算法进行路径搜索计算,其时间复杂度是O（n2）（n为网络节点数量）,即当面临百万节点的复杂网络拓扑时,启发式搜索算法的搜索耗时将会呈指数级快速增长,无法完全满足工程技术需求．通过理论分析与实验数据证明应用二叉堆的启发式搜索算法对于长路径,大搜索空间的搜索应用时表现出良好的时间线性,其时间复杂度是O（logn）（n为Openlist的节点数）,没有出现常规启发式搜索算法应用时搜索时间爆炸式增长的情况,具有较高的性能和效率,对工程实践有一定的实用参考实用价值．     

低复杂度MIMO雷达波达方向的估计方法研究

为了降低MIMO雷达的运算复杂度,研究了基于对回波信号降维处理算法和基于子空间重构的信号子空间重构（SsR）算法的两类波达方向（DOA）估计方法．通过对5种算法的对比和仿真分析可知：RD—ESPRIT算法相比其他空间谱搜索算法,对降维矩阵的选择较敏感,更强调降维后阵列流型的旋转不变性;RD-求根算法、RD—MUSIC算法和RD—Capon算法则有更好的角度估计性能;RD-ESPRIT算法和RD-求根算法运算量相比其他三种算法低一到两个数量级;RD—ESPRIT算法运算复杂度最小．     

对称Toeplitz—plus—Hankel矩阵特征值的快速算法

利用了n阶对称Toeplitz—plus—Hankel矩阵的结构特点和对称性,给出了计算该类矩阵所有特征值的一个快速算法．该算法的计算复杂度为o（n^2 logn）,比文献[1—2]所给的算法来得少．     

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

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

单机分族分批排序的最小误工个数问题

文章研究了同一族内,给出并证明了其最优排序的性质。对工件到达时间和工期相一致时的情形,得出了一个时间复杂性为O（mb（n/m）^2m）的动态规划算法。     

半定锥上具有O(n1/2L)复杂性的Mehrotra型预估矫正算法

文中将文献线性规划中的Mehrotra型预估矫正算法推广到半定规划,提出一种求解半定规划问题的Mehrotra型预估矫正算法,该算法基于NT方向,证明了该算法具有目前最好的的迭代复杂性O(n^1/2L).     

Mod 2n加法和减法的代数正规型

文献[1]给出了从n元布尔函数f的代数正规型得到f（X＋Y mod 2^n）和f（X＊Y mod 2^n）的公式,其中Y是常数。基于mod 2^n加法进位比特的性质,给出了求X＋Y mod 2^n或X-Y mod2^n的n个分量函数的代数正规型的方法。其总的计算复杂度分别为O（2^n）（或O（3n））。远远低于经典的用真值表计算布尔函数代数正规型的算法[2]。使用文献[2]的算法仅得到X＋Ymod 2^n（或X-Y mod 2^n）最高位的计算复杂度就达O（2^n＊22 n）。     

一种基于后缀数组的多重复模式匹配算法

要在海量的信息中进行多重复模式的查找,应用一般的查找方法所需O（n2）的复杂度.为了提高模式查找算法的效率,提出了算法Epattern searcher H.该算法是采用能节省空间占用的后缀数组数据结构来实现,同时又运用过滤算法的思想而设计,从而提高算法的运行速度.这里针对英文小说高频词的查找对算法进行测试,可得到时间复杂度为O（n）实验结果.     

基于权值跳表的分布式数据定位策略与实现

为了克服现有的定位技术对快速查找存储数据算法性能的限制,提出一种基于权值跳表的分布式数据定位(Distribute Data Location Priority Skip List,DLPSL)策略,以解决数据定位效率问题。在跳表节点中加入权值,使定位率高的存储节点优先被找到,缩短查找路径,提高定位效率。系统性能分析表明,DLPSL中节点的插入、删除和定位比单链表存储结构和跳跃图效率都高,其时间复杂度为O(logn),空间复杂度为O(n)。     

解动态约束规划问题的差分进化算法

动态约束规划问题求解的困难在于如何处理问题的约束及时间(环境)变量.本文给出了求解一类定义在自然数集上的动态约束规划问题的差分进化算法,该方法借助于问题的约束条件设计了一种新的适应度函数及选择算子、同时给出了一种带一维不精确局部搜索的变异算子极大地增强了群体的多样性、提高了算法跳出局部最优的能力.数值试验表明,该算法性能稳定性较好,收敛速度较快,全局搜索能力较强,其对动态非线性约束规划问题求解是有效的.     

寻找平面上点的凸壳

对格雷厄姆算法进行了改进,编程实现寻找平面上n个点的凸壳,并通过1次循环就找出所有凸壳的顶点.该算法的空间复杂度为O(n-3),其时间复杂度在最坏情况下虽然无法突破O(nlogn)的理论下限,但在最好情况下已达到线性水平.     

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

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