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

给出了求以秩为n的m×n Cauchy型矩阵Moore-Penrose逆的快速算法,该算法的计算复杂度为O(mn) O(n2).     

多路插入排序算法

对时间复杂性为O(n2)的传统直接插入排序,提出了一种多路直接插入排序算法,给出了相关算法描述及性能分析;讨论了新算法中的插入路数与时间复杂性的关系,得出了当路数为O√n时,时间复杂性有最小值O(n3/2)的结论;最后将多路直接插入排序算法与已有的一些直接插入排序算法进行了比较,结果明显优于已有算法.文中的算法思想同样适用于折半插入排序.     

有限群上几个问题的算法及复杂度分析

本文讨论有限群上几个计算问题。我们设了一个O(n~2)时间的算法去查找n阶Abel群的基底(把n阶Abel群分解为循环P群的直积)。给出了复杂度为O(n~2log_2n)的n阶Abel群的检验算法。证明了n阶Abel群的同构检验可在O(nlOg_2n)时间内完成。最后,我们讨论定义在有限群上的旅行售货员问题:证明了该问题是NP完全的,并给出了一个O(m·n~2·2~n)时间的算法求解它。     

一种基于数据块交换的快速稳定原地归并算法

与其它排序算法相比.二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个 有序子表,经典算法有2种/第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动/第 二种算法是原地的.但完成归并需要O(m+n)次比较和O(m*n)次移动,提出了一种基于块交换的快速 稳定原地二路归并算法.实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数.     

拉格朗日插值多项式的一种并行算法

提出在机群系统并行环境下的构造拉格朗日插值多项式的一种并行算法.该算法以n个节点(x0,y0),(x1,y1),…,(xn-1,yn-1)的拉格朗日插值多项式公式为基础.当处理机数量为n2时,它的时间复杂度为3log(n) O(1);当处理机数量为p2(p相似文献   

对随机排列落表剖分算法的一个改进

列车编组作业中要求将一个任意排列的车列依到站的先后次序重新排列,数学上将其抽象为随机排列的顺序剖分。落表算法是已有的最优算法。本文给出的算法得到与落表算法相同的结果,而对一类随机排列,其时间复杂度低于落表算法。1 落表算法的一些性质 以S(m,n)表示含有几个不同数字,且相邻数字不相同,长为m的所有排列的集合。当m=n时,落表算法的时间复杂度为O(n2)阶。 定理 给定　　S(n,n)　随机等可能地取自S(n,n).随机变量X表示求P　()所需要的比较次数,则EX=O(n2),VarX=O(n3). 证明 取　为顺序排列,并且记P(X=k)=P　k,当X=k时,若a=1,…     

一种基于数据块交换的快速稳定原地归并算法

与其它排序算法相比,二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个有序子表,经典算法有2种。第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动。第二种算法是原地的,但完成归并需要O(m+n)次比较和O(m×n)次移动。提出了一种基于块交换的快速稳定原地二路归并算法。实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数。     

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

通过构造特殊分块矩阵及其三角分解给出了求秩为n 的m×n阶Loewner型矩阵为系数阵的线性方程组极小范数最小二乘解的快速算法, 该算法的计算复杂度为O(mn)+O(n²), 而一般方法的计算复杂度为O(mn²)+O(n³) .     

循环矩阵开平方的快速算法

利用快速傅立叶变换 (FFT) ,给出了 n阶循环矩阵开平方的一个快速算法 ,计算循环矩阵的同型平方根矩阵 (平方根矩阵也是循环矩阵 ) ,证明了同型平方根矩阵的个数为 2 n ,它是关于 n的指数函数 ;计算一个同型平方根矩阵的时间复杂性为 O(nlog2 n) ;计算全部同型平方根矩阵的时间复杂性为 O(n2 n) .     

Max-plus代数中analogy-transitive矩阵及其本征问题

定义一类analogy-transitive矩阵,讨论其基本性质,给出判定一个矩阵是否为analogytransitive矩阵的判定定理及算法,最后讨论关于analogy-transitive矩阵的本征问题.对于analogytransitive矩阵,存在一个O(n2)的算法计算其唯一本征值λ(A)和所有本征向量x=(x1,…,xn)使得max j=1,…,n(aij+xj)=λ+xi(i=1,…,n).该结果较一般情况下O(n3)的算法有所改进.     

求解一类T型线性方程组的快速算法

本文首先给出一个求解一类T型线性方程组的快速串行算法,它的复杂性是O(nlogn),比目前最好的O(n~2)算法复杂性要低。接着又指出了它的并行计算方案,在n台处理机的条件下,计算步数不超过O(logn),速度倍数是O(n),效率是O(1)。     

一种面向HPC Cloud系统的在线作业调度算法

针对HPC Cloud中的作业之间对网络I/O资源的竞争问题,提出了一种基于动态规划算法、二分搜索算法和网络最大流算法的在线作业调度算法——DBMF算法.DBMF算法专注于物理节点上网络I/O的负载均衡,通过物理节点之间的网络I/O负载均衡来减少对网络I/O资源的竞争.通过与FCFS和RSF算法进行对比,DBMF调度算法有效提高了HPC Cloud的系统负载,减少了作业之间对网络I/O资源的竞争.     

找K个最小生成树的并行算法

基于SIMD 机器——一种可以同时读但不可同时写的共享计算模型(CREW-PRAM)给出了找K 个最小生成树的并行算法,此算法需O(log~2n+Klogn~*)时间及O(n~2)处理器;而基于可以同时读、写的更强计算模型(CRCW-PRAM),求K 个最小生成树仅需O(Klogn)时间及O(n~2)处理器,这里n 是图的顶点数.     

用于IC版图运算的O(N)排序算法

扫描线算法是集成电路版图运算的主流算法,排序在其中占有相当大的工作量．针对集成电路版图的特点,提出一种线性的排序算法,其时间复杂度为Ｏ（Ｎ）,比通常的快速排序算法时间复杂度（Ｏ（ＮｌｏｇＮ）低,适用于基于扫描线算法的集成电路版图运算．对于层次式设计的版图,该算法更具优越性     

圆饼装填问题的并行算法

圆饼装填是一个将多个芯片设计组合到一个圆饼上，构造费用通过几个设计分担而减少的过程。本文在ＳＩＭＤ－ＣＲＥＷ并行计算模型下，通过修改Ｐｒｅｐａｒａｔａ并行排序算法及其用到的Ｖａｌｉａｎｔ并行归并算法，给出了分配２个设计到一个包的基本圆饼装填问题ＢＷＰＰ的并行算法，在Ｏ（ｎ＾１．５）台处理机上，算法的时间复杂性是Ｏ。     

求凸壳顶点的一种算法

提出了一种求平面有限点集凸壳顶点的算法,并分析出该算法的时间复杂性是线性次乘法和O(nlogn)次两个数的比较。     

拟希尔伯特阵和一般阵相乘的快速串行与并行计算

本文给出了拟希尔伯特阵和一般阵相乘的快速串行与并行算法。对于串行计算,时间复杂性是O((nlogn)~2),对于并行计算,在有n台处理机的条件下,其计算步数是O(nlog~2n),而效率是O(1)。     

二叉树CreateBTree算法的改进

在分析二叉树的CreateBTree算法的基础上，利用线性探测再散列方法对CreateBTree算法的中序遍历序列进行预处理来改进CreateBTree算法，使得改进后的CreateBTree算法在最差情况下，时间复杂度由O(N^2)降为O(N)。     

对Satoh算法的改进

在Satoh算法的基础上,利用对范数的有效计算给出了一个计算特征为2的有限域上椭圆曲线阶的算法,其计算复杂度为O(lg4.5q),存储空间为O(lg2q).     

求解货郎担问题的几何算法

提出了求解货郎担问题的一种几何算法，它的时间复性为：Ｏ（ｎ＾３／ｍ）次比较，Ｏ（ｎ＾２）次求距离运算与Ｏ（ｎ＾３／ｍ＾３）次加法运算，其中ｎ，ｍ分别为点集的点数和凸包顶点数。