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

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

基于均值查找的快速中值滤波算法

针对传统中值滤波算法时间复杂度高、运行速度慢,难以满足大型图像数据实时处理的问题,提出了一种快速中值滤波算法,将确定中值元素的过程由排序运算转换为基于均值对集合的二分查找,算法不依赖于滤波窗口的形状以及相邻窗口的相关信息,有效提高了中值滤波的执行效率,使传统中值滤波算法的时间复杂度由O(nln n)下降至O(n).实验中,该算法应用于大型图像序列的滤波处理,其运算速度提高到传统中值滤波算法的3倍以上,并且算法运行时间仅随滤波窗口大小线性增长,可以满足大尺度滤波窗口对大型图像数据实时处理的需求,具有显著的实际应用价值.     

求GF(pm)上周期为kn的序列线性复杂度的快速算法

提出和证明了求GF(p^m)上周期为kn的序列线性复杂度和极小多项式的一个快速算法, 其中p是素数, gcd(n, p^m-1)=1且p^m-1=kt, n,k与t均为正整数．该算法推广了陈豪提出的求GF(p^m)上周期为3n的序列线性复杂度的一个快速算法, 其中p是素数, gcd(n, p^m-1)=1且p-1=3t, n与t均为正整数．结合一些已知的快速算法, 可以快速计算GF(p^m)上周期为kn的序列线性复杂度, 最后给出一个具体例子．     

离散傅里叶变换在序列线性复杂度快速算法中的应用

利用广义离散傅里叶变换对GF（2）上周期为n2∧υ(gcd(n,2)=1)序列进行了研究，给出了求其周期为n2∧υ序列线性复杂度的快速算法，并得到了关于F[D]上多项式的Hasse导数一些新结果。     

2n-周期二元序列的6-错线性复杂度

线性复杂度和k-错线性复杂度是度量密钥流序列的密码强度的重要指标.该文通过研究周期为2n的二元序列线性复杂度,基于Games-Chan算法,讨论了线性复杂度为2n-1的2n-周期二元序列的6-错线性复杂度分布情况.在大多数情况下,给出了对应6-错线性复杂度序列的计数公式,并且指出了参考文献中的一个重要错误.     

二元周期序列的5错线性复杂度

线性复杂度和k错线性复杂度是度量密钥流序列的密码强度的重要指标。该文通过研究周期为2n的二元序列的线性复杂度,将k错线性复杂度的计算转化为求Hamming重量的最小的错误序列,基于Games．Chan算法,分析了线性复杂度为2n,周期为2n的二元序列的5错线性复杂度的分布情况,给出了5错线性复杂度为2n-3,2n-3＋1和2n-2-2n-4的二元序列的计数公式,并通过计算机编程进行了验证。     

二元周期序列的k-错线性复杂度研究

线性复杂度和k-错线性复杂度是度量密钥流序列的密码强度的重要指标.通过研究周期为2n的二元序列的线性复杂度,该文提出将k-错线性复杂度的计算转化为求Hamming重量最小的错误序列.基于Games-Chan算法,讨论了线性复杂度为2n-m的2n-周期二元序列的k-错线性复杂度分布情况.当(m,k)=(5,4),(6,4...     

M(o)bius立方体上一个新圈的构造算法

研究了求n维Mobius立方体中Hamilton路的过程，给出了求n维Mobius立方体中长度为l的圈的算法（n≥2，4≤l≤2^n)。该算法的时间复杂度为O（l)，从而改进了樊建席等给出的时间复杂度O（NlogN)的算法。     

散列快速排序

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

链表结构快速排序算法

快速排序算法是目前较好的排序算法,但它有两个缺点。其一是排序结果不稳定,其二是当要排序的数据基本有序时,速度反而最慢,达到O(n~2)。本文使用链表结构存贮数据并使用相应的链表运算算法,从而实现了结果的稳定性。本文还提出了逆序计数法并使用了倒链算法,使已经有序的子表不再进行分割,从而使基本有序的数据的排序速度可达O(n)。本文严格证明了该算法的稳定性和在各种情况下的排序速度,说明该算法优于原快速排序算法。     

一个高效散列排序算法

文中给出一个Ｈａｓｈ函数及在２Ｎ空间中进行散列排序的算法。证明最该Ｈａｓｈ函数的存在和单调性,算法在装载因子为１／２的条件下具有Ｏ（Ｎ）的时间复杂性。给出一组随机数据和用不同算法进行排序的比较,测试结果表明,该算法是高效的。     

OLAP中基于GPU的中位数计算算法

针对联机分析处理(online analytical processing, OLAP)中的整体型聚集函数中位数,提出基于图形处理单元(graphics processing unit, GPU)的GPU-Median算法,通过对数据进行划分,分段排序,不断裁剪全局中位数之前的数据,对未裁剪的数据进行合并,得到最终的中位数,避免了全局的排序时间。提出GPU-Median+算法,对GPU-Median算法进行优化和扩展,使用CPU与GPU协同作业实现聚集操作,利用GPU处理每个队列的数据,CPU处理全局数据。试验和分析证明,相比CPU算法,GPU-Median+算法将中位数计算的时间复杂度从O(n²)降低到了O(n);相比GPU上的基数排序算法,GPU-Median+算法的计算时间减少了三分之一。该算法的应用使得GPU计算OLAP中的整体型聚集函数时,发挥出更加优良的并行计算能力,为提升OLAP的查询性能提供了新的思路。     

一种确定高阶Delaunay三角网中可用k—OD边的算法

目的构建高阶Delaunay三角剖分方法的数字地形模型,有效地减少局部极值问题,使得地形模型能更好地反映原始地形的真实面貌．方法提出了一种确定高阶Delaunay三角网中可用k-OD边的方法,该方法首先在任意边uv的两侧分别确定两点,使每个点与uv边形成的三角形的外接圆不包含同侧的点,若这两三角形都为k—OD三角形,则uv边是可用k—OD边．结果用Visual C＋＋实现算法,通过实验验证了算法的有效性,对于具有n个点的点集P,在时间O（nk^2＋nklogn）内可以计算出所有的可用k—OD边．结论选择合适的可用k—OD边生成相应的高阶Delaunay三角网来模拟实际地形,可以有效地减少局部极小的数量,使地形模型更接近于实际地形．     

用于RFID中间件的内存数据库结构研究

内存数据库(MMDB)是射频标签(RFID)中间件能够实现实时过滤、分组、计数等操作的关键.针对大规模RFID应用中通用的以T树为索引结构的MMDB不能得到很好的效率的问题,在详细分析RFID应用的数据特性的基础上,总结出RFID应用的数据及其操作特征,提出一种全新的算法,并改进了MMDB的索引结构.算法与MMDB的索引结构相结合,使得内存数据库在支持所有符合EPC Global标准的接口操作的基础上,将需要保存的数据量减少到最低,能保证每个标签只有一条记录.在RFID应用所特有的大量范围查询上,查询的时间复杂度降低到了O(n).     

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

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

一种低复杂度的雷达信号分选方法

针对现有支持向量聚类算法在雷达信号分选应用中复杂度高、用传统有效性指标难以描述最佳分选效果的问题,研究了基于锥面聚类分配的支持向量聚类算法;利用该算法依赖于特征空间和数据空间近似覆盖的特性,避免了邻接矩阵的计算.提出了基于相似熵的有效性验证指标,应用信息熵的理论描述了类内聚集性和类间分离性.仿真结果表明,该方法在保证分选正确率的同时,可以有效降低计算复杂度,在一定程度上满足了情报侦察系统的实时性和准确性要求,具有较强的实用价值.     

空情仿真软件中外部排序算法的探讨

在一般外部排序算法的设计中，归并路数Ｋ的选择是很关键的，它直接影响一个算法程序执行的时间效率．本文介绍ＥＫ－３０１系统空情仿真软件中的多批航路数据流的分批合批及排序方法，并通过对数据分批合批处理算法的时间复杂度分析，就数据流的外部排序归并路数Ｋ值的选择进行了讨论，从而在仿真软件的设计中得到一个较理想的外部数据排序及分批合批处理算法     

基于混沌PSO或分解的二维最小误差阈值分割

为了进一步提升现有的二维最小误差阈值分割快速递推算法的运行速度,提出分别基于混沌粒子群优化（PSO）和分解的2种二维最小误差阈值分割算法.第 1种算法利用混沌粒子群优化算法搜寻二维最小误差法的最佳分割阈值,且在迭代过程的适应度函数计算中引入递推算法,大大减少了冗余计算;第2种算法将二维最小误差法的运算分解成一维最小误差法和一维最小类内对数方差法的运算,计算复杂度由二维递推算法的O(L2) 进一步降为O(L).实验结果表明,提出的2种算法能够在分割效果达到或优于现有的二维最小误差阈值分割法的同时,大大加快运行速度.