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

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

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

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

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

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

PMC模型下超立方体的一种条件诊断算法

诊断是一种提升互连网络可靠性的常用手段．条件诊断是假设系统中任一节点的所有相邻节点不会同时发生故障,这种诊断大大提高了诊断的有效性．提出一种在PMC模型下超立方体的条件诊断算法,通过广度优先搜索遍历整个超立方体,在遍历过程中通过相邻节点之间的诊断结果将超立方体节点分成若干个集合,再通过集合之间的关系和集合中所含元素的数量识别出故障集合和无故障集合．对于n维超立方体,节点数为N,该算法的时间复杂度为O(N²)．     

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

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

超立方体网络广播容错路由算法

研究了具有大量错误结点的超立方体网络中的广播容错路由算法，假定Hn是一个局部3维子立方体连通的n维超立方体网络，并且每一个基本的3维子立方体中分别最多有1个和2个错误结点，从理论上证明了在最坏情况下基于shhouing广播通信模式的广播容错路由算法分别经过最多1.5(n-1) 和2（n-1)时间步，就可以将源结点的信息广播到Hn中的所有正确结点中，通过实验验证了在均匀和独立的错误结点分布情况下广播时间步的上界实际上只有n 1，支持了理论分析结果。     

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）。     

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

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

基于最近邻优先的高效聚类算法

针对高维空间中任意形状的多层次聚类问题，基于“同类相近”的思想，提出并实现了最近邻优先吸收聚类算法NNAF算法。证明了最近邻点搜索定理，基于这一定理又提出了SNN(Searching Nearest Neighbors)算法和GSNN(Grid-based Searching Nearest Neighbors)算法，其时间复杂度为O(n*log(n))，当用扫描图像所得数据时，时间复杂度会降为O(n)；而使用传统的搜索算法，时间复杂度为O(n^2)；提出了实现任意形状高维空间聚类的NNAF算法，时间复杂度为O(n)；提出了MLCA(Multi-layer Cluster Algorithm)算法并证明了两个相关的定理，在改变阈值后重新聚类时，使用MLCA算法可以节省90％以上的时间。实验结果显示，以上算法适应于任意形状的高维空间数据的聚类，可以有效过滤噪声数据，且用户需要的先验知识少、可快速获得各种层次的聚类结果。     

k-means聚类问题的改进近似算法

研究了Ostrovsky给出k-means问题的（1＋ε）-近似算法,针对算法中取样参数小的以及枚举数量大的不足,证明了可以选择一个更大的取样参数减小取样点集,基于随机算法,提出新的枚举策略减少枚举数量。本文分析了算法的成功概率。改进算法的期望时间复杂度为O（2O（kα2/ε）dn）,其中d、n分别为问题实例的空间维数和输入点个数,α是小于1的分隔系数。算法的成功概率为121-e-21εk（1-O（α））。与Ostrovsky给出的算法相比,算法的运算效率得到很大的提高。