三角形Toeplitz系统的并行求逆算法

<正> 本文给出了规模为n的三角形Toepfitz 系统的一种并行求逆算法。该算法所需处理机的台数p=n,并行时间步数T_p=O(log_2~2n),从而速度倍数s_p=O(n/log_2n)。另外,我们对多项式快速除法也作了相应的并行处理,并给出了三角形T 矩阵逆的一个显示表达式。     

齐一并行排序算法

本文给出的算法,是一个适合并行处理的排序方法.它有控制规则简单,整体对称,层次结构清晰,满足递归特征等许多优点.它对n个元素排序时并行深度为1/2log_2n(log_2 n+1),并行宽度为n/2.该算法可直接应用于并行计算,用VLSI线路设计并行排序网络等方面.     

虫孔路由二维网孔机器上的最优图论算法

连通分量和最小生成树是图论中的两个基本问题 ,在许多领域都有很多应用 .对于顶点数为 n的图和规模为 p× p的虫孔路由二维网孔机器 ,该文针对 p n和 n

相似文献   

并行双调排序算法的有效实现及性能分析

排序是计算机中最常见的操作之一，双调排序是一个非常著名的排离算法，也是最早的并行排序算法，又调排离对排序算法的研究具有非常深远的影响，基于双调排序算法的基本思想，介绍了双调排序在分布存储的并行计算机环境下的一种有效实现方式，采用局部多对多通信替换全局通信，很好地解决了双调排序中的通信问题，算法的计算复杂度为⊙n/p(logn log^2p)，其中n为待排序的关键字个数,p为处理器数，算法在二维网孔结构上通信时间复杂度达到了O（2.12132√p.n/p）其量级达到了理论上的下限，分析结果表明，双调排序算法也具有很好的通信性能和可扩展性。     

Multisets排序的最优并行算法

排序是一个既有十分重要的理论意义又有广泛的实际应用价值的问题 ,其中 ,Multisets排序问题是指对只有k个不同关键字值的n个数据 (记录 )进行排序 ,0 相似文献   

一种基于PVM的Multisets并行归并算法

Multisets排序是指对具有k个不同计算机系统、基于消息传递环境下,以加法运算为基础的稳定的归并并行算法,该算法实现对Multisets的排序,其时间复杂度为O(n/p log p k log p 4p n/2).     

全CPLAs16×16位快速乘法器的设计

本文给出了一个16×16位快速补码乘法器的设计方案。这个乘法器中的部份积采用SD数表示形式和SD数的加法算法;部件全部采用高速、低功耗的CPLA作为基本元件、并给出了由CPLA构成的全并行加法器T.P.A.的逻辑设计;结构上采用由T.P.A.组成的加法二叉树。这类乘法器的一次乘法时间是比例于log_2n,是O(log_2n)级乘法器,它的一次乘法时间可期望在120ns以下。     

dBASE数据库中一个快速实现自然连接的方法

在dBASE中,以JOIN命令实现二个分别具有m、n个记录的库文件的连接,其运行时间复杂性为O(m×n);本文给出一个以dBASE命令编程快速实现自然连接的方法,其运行时间复杂性为O((m+n)log_4n)。     

Radix Sort——复杂度为O（n）的排序方法

在每一本讲算法的教科书中差不多都有讲排序的方法，从最初的选择排序、冒泡排序，到哈希排序、快速排序、堆排序，二叉树排序等等。一般的认为，通用排序中．最低的算法复杂度为O(n&#183;LoG(n))，n是待排序的元素个数。那么有没有比这更快，算法复杂度更低的排序算法呢?在本文中，大家将会看到一种算法复杂度为0(n）的     

多队列快速排序

快速排序算法的平均时间小于所有已知的O(nlogn)排序算法。它的平均时间是O(nlogn),最坏情况为O(n~2)本文提出的算法对n个元素的排序时间为O(nlogm),其中其最佳性能为O(n)在M 16计算机上运行的结果符合文中给出的算法分析     

线对象邻接关系快速重构算法

给定向量化坐标,计算n个线对象两两邻接关系,普通算法时间复杂度为O(n*n);理论最好时间复杂度为O(C),其中C是邻接关系的基数。基于散列桶,给出了建立线对象邻接关系的快速算法,其平均时间复杂度为O(n(1+1/r)),r为算法分配的桶数量与n的比,空间复杂度为O(n)。证明了若不允许使用额外空间,则不可能使用排序算法解决该问题;给出了允许使用额外空间条件下的两遍排序算法,时间复杂度为O(n(lbn+1+2/r))。应用表明快速算法比普通算法速度提高1~3个数量级。     

一种基于HASH变换的循环散列分档排序算法

在数据排序问题中,各种分段快速排序算法[3～11]只有对特定的数据分布类型或者符合ΔM相似文献   

网孔处理机阵列上最小生成树算法

已知一加权无向图G(V,E),|V|=n.本文基于网孔处理机阵列,运用分而治之策略和数据归约技术给出了一种新的最小生成树算法.此算法需O(n~2/p)时间,使用了O(p)个处理机(1≤p≤n).当p=n时,此算法仅需O(n)时间和O(n)处理机.而目前基于同一计算模型上此问题的最好算法需O(n)时间和O(n~2)个处理机,因而这里给出的算法在使用处理机数目方面改进了O(n)因子.     

二分图最大匹配问题的分布式算法

本文基于异步通讯网络,对二分图最大匹配问题,建议了两个分布式算法。其中第一个简单算法的通讯复杂性为O(n(n~2+m))、时间复杂性为 O(n~3);第二个算法的通讯复杂性为O(n~(1/2)(n~2+m))、时间复杂性为O(n~(5/2)),这里n和m分别为二分图的结点个数及边的数目。关于这一问题的分布式算法目前尚未见诸报导,这里建议的算法很可能是此问题的第一个分布式算法。     

单向链表快速排序算法

单向链表广泛应用于动态存储结构,当前单向链表的排序算法普遍效率偏低,而平均效率最高的快速排序算法并不适用于单向链表。基于分治策略,使用递归方法,通过重新链接单向链表节点,提出了用于单向链表的快速排序算法,其平均时间复杂度为O(nlog2n),辅助空间复杂度为O(0),平均递归栈空间复杂度为O(log2n);同时,进行了算法分析和实验测试,其效率较其它单向链表排序算法有较大提高,且较传统基于线性表的快速排序算法也有一定提高。研究结果解决了当前单向链表排序效率较低的     

受限网络模糊对象最近邻查询

针对网络空间中有范围约束、不确定对象的最近邻查询问题,提出范围受限的网络空间模糊对象最近邻查询概念,并根据查询顺序的不同,给出NN-R查询算法和R-NN查询算法。两种算法均采用网络位置信息与连接信息分别存储的方式,使用聚类文件进行组织,减少I/O操作。NN-R算法在近邻查询过程中利用查询对象与受限范围的α-距离作为约束,缩小搜索范围。R-NN算法将受限范围内查询对象的欧氏近邻作为候选对象,利用欧氏距离的下界性与易求性降低时间复杂度。两种算法时间复杂度分别为O((log_(m1)|E|+(|V~*|m3+1)log_(m2)|V|+|E|+|V|log|V|+n(lgn+1))和O(log_(m4)n+(k+1)log_(m1)|E|+|E|+|V|log|V|)。实验结果表明,在各自适用条件下,两种算法均有较好的性能。     

单向链表快速排序算法

单向链表广泛应用于动态存储结构,当前单向链表的排序算法普遍效率偏低,而平均效率最高的快速排序算法并不适用于单向链表。基于分治策略,使用递归方法,通过重新链接单向链表节点,提出了用于单向链表的快速排序算法,其平均时间复杂度为O(nlog2n),辅助空间复杂度为O(0),平均递归栈空间复杂度为O(log2n);同时,进行了算法分析和实验测试,其效率较其它单向链表排序算法有较大提高,且较传统基于线性表的快速排序算法也有一定提高。研究结果解决了当前单向链表排序效率较低的问题。     

堆选排序算法时间复杂性的改进

堆选排序算法的时间复杂性T_(11)=2·nlog_2~n+O(n)本文提出的一种算法实现了一对堆选排序的时间复杂性的改进。我们将证明,同样对n个元素进行排序,它耗费的时间不超过堆排序的一半。     

基于流水光总线阵列上的快速可扩展并行排序算法

在Y．Pan提出的基于流水光总线阵列模型(LARPBS)上使用N个处理器对N个元素进行排序在最好情况下以O(logN)时间，最坏情况下以O(N)时间完成的并行排序算法的基础上，提出了一种LARPBS模型上的可扩展的快速并行排序算法，对N个元素进行排序，使用p(1≤P≤N)个处理器在最好情况下以O(NlogN／p)时间，最坏情况下以O(N^2／p)时间完成排序。另外还提出了一种LARPBS模型上改进的快速高效并行排序算法，该算法对N个元素进行排序使用N个处理器在最好情况下以O(log√N)时间、最坏情况下以O(√N)时间完成排序。     

深度优先稳定原地归并排序的高效算法

基于分治策略,使用深度优先的方法,提出了一种用于线性表的稳定原地归并排序算法,其时间复杂度为O(n lb n),辅助空间复杂度为O(1),递归栈空间复杂度为O(lb n),同时进行了算法分析和实验测试。实验结果表明,该算法效率较STL中的稳定原地归并排序算法有67.51%的提升,解决了稳定排序算法中要么时间复杂度高要么空间复杂度高的问题。