有限群上几个问题的复杂性分析

本文,我们设计了一个O(n~2)时间的算法,去求n阶Abel群的基底;即把n阶Abel群分解为循环P群的直积。接着,我们讨论有名的群同构检验问题,洪加威O(n)时间的n阶Abel群同构检验算法也列入本文(洪加威教授提供)。最后,我们证明有限群上流动售货员问题是NP-完全的;并给出O(m~2·n·2~m)时间的算法求解这个问题,这里n为群的阶,m为图中结点个数。     

LCS问题的一种新算法及其推广

求解LCS(Longest Common Subsequences)的通常算法,空间和时间的复杂性为O(n~2)。本文中提出的算法,空间复杂性为O(n),时间复杂性为O(n)～O(n~2),时间复杂性取决于序列中符号的分布,本算法便于并行处理及制成微处理器。 为了应用于模式识别,推广到WLCS(Weighted Longest Common Subsequences)以及LCSM(Longest Common Submatrix)。 给出了有关的定理,及算法正确性的证明。     

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

已知一加权无向图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)因子.     

Hypercube多处理器上图的最优算法

已知一个无向图G(V,E),|V|=n.本文在SIMD机器-Hype-rcube上提出了计算图的连通分支和最小生成树的两个最优算法.若Hypercu-be由P个处理器组成,则上述两个算法的时间复杂性都是O(n~2/p),1≤p且PlogP≤n.     

关于Vandermonde矩阵的串行与并行复杂性

为n+1阶Vandermonde矩阵,简称V阵。 本文首先给出求解相应线性代数方程组(简称V型方程组)的递推算法。算术运算总次数为O(n~2)级,接着进一步利用快速插值算法导出求V阵逆的O(n~2)算法,并分析了这两种算法的并行时间复杂性。     

n个元素分类(sort)的一个算法

本文给出的是分类 n 个元素的一个递归算法,其时间复杂性为n log n-5/4 n+1og n~(1/2)+C,这个值已经和分类问题的理论下界相当接近。目前所知的和它同级的分类法,如堆分类法(Heapsort)和合并分类法(Mergesort)等,虽然都是 O(nlogn)级的,但所需比较次数都比本文提供的算法多。本文共分三部分:1.最少插入分类法2.时间复杂性3.作者的猜想     

复矩阵乘法的并行计算

<正> 在矩阵计算中矩阵乘法是最基本的。一个好的矩阵乘法算法往往能大量节省求解线代数问题的计算时间。如Strassen算法的问世就使线代数方程组求解、行列式求值等的运算量,从0(n~3)下降为O(n~(2.81))。不少领域中经常遇到复矩阵的乘法,而到目前为止讨论这一问题的并行算法的文章甚少。本文提出两类计算方法并讨论了各种算法的性能、并行时间复杂性及其误差分析。一、化为实短阵乘法的算法类众所周知,若A、B、C、D是实域上n阶全矩阵环中的元素,则成立互等式(A+B_i)(c+D_i):(Ac-BD)+i[(A+B)(c+D))-Ac-BD] (1)     

平面上简单多边形平移时确定碰撞部位的最优算法

本文提出一种时间复杂性为O(m+n)的算法,在一个多边形的凸包不和另一个多边形相交的条件下,该算法可确定二个多边形是否相撞,在相撞时可确定全部碰撞部位.本文还证明了确定碰撞部位问题算法的时间复杂性的下界为O(m+n),因而本文提出的算法是最佳的.     

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

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

并行递归筛选选择算法

本文提出了一个基于动态分治和递归筛选方法求解选择问题的并行算法,描述了其在无存取冲突SIMD-SMC机器上的实现.所给出的算法对于在n台处理器上求解从n个数中选取前m个或第m个最小(或最大)者的问题(m相似文献   

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

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

相似文献   

最长公共子序列问题的改进快速算法

现在几个最常用的解决最长公共子序列(LCS)问题的算法的时间复杂度分别是O(pn),O(n(m-p)).这里m、n为两个待比较字符串的长度,p是最长公共子串的长度.给出一种时间复杂度为O(p(m-p)),空间复杂度为O(m+n)的算法.与以前的算法相比,不管在p<相似文献   

第18届全国信息学奥赛（NO12001）解题报告

第一题《食物链(eat)》解题报告 摘要 算法＃ 算法1 算法2 时间复杂度 O(nlogn+m) O(mα(n+m,m)+n) 空间复杂度 O(n) O(n) 特殊数据结构 分离集合 分离集合 问题转述 给定某个含有n个元素的集合S,其中每个元素都具 有三种属性(A、B或C)中的一种,是根据已给出的各 个元素之间的相对关系集R来确定某两个元素之间的相对关系。 分析在读题之后我们可以简单地得出处理一条输入的流程 图如下:     

在线性处理机阵列上求MCST的并行算法

本文给出一种在P个处理机线性阵列上求MCST(最小代价生成树)的并行算法,记为OLA-MCST.证明了在整个1≤P≤n范围内其时间复杂性均为O(n~2/P);特别地,当P=n时,为O(n).这是在本模型下使用n个处理机时的最优性能.     

关键路径的稀疏矩阵求解算法

求解AOE网的关键路径算法一般基于拓扑排序，虽然具有较好的时间复杂度(O(n+e))，但由于必须进行拓扑排序，同时还要进行拓扑逆序扫描，使得算法本身比较复杂。针对这个问题提出了一个算法，算法采用了稀疏矩阵作为数据的存储结构，为防止关键路径丢失，采用队列方式进行操作。同经典算法相比，该算法简单，时间复杂度相近(O(n+e/n))。     

k-median问题反向贪心随机算法

k-median问题的近似算法研究一直是计算机科学工作者关注的焦点。基于均衡限制条件,利用反向贪心策略,给出求解该问题的随机近似算法。证明该算法以较大的概率满足其近似性能比的期望值为(3+O(ln(ln(k)/α))。该算法的时间复杂度为O([kαln(k)]2(n+m)),其中n和m分别代表设施集合以及客户点集的大小。最后,通过计算机实验验证了k-median问题的反向贪心算法的实际计算效果。     

λ-连通分割和最优区域分并分割算法

本文提出适用于多维灰度图象的λ-连通分割算法,其计算时间为0(m|∑_m|);这里m为空间∑_m的维数.我们对λ-连通分割作了误差分析,并利用长度k-局部受限的概念,证明当图象在∑_m中的连通量不大于(1/2)|∑_m|时,k必须大于O(m-1)ln n)且几乎不需要超过O((m+1)ln n). 我们改进了经典的区域分并(四叉树)分割方法,得到其时间复杂性为O(|∑_m|·log_2|∑_m|)的算法,并从理论和应用两方面对这两种方法作了比较.     

多队列快速排序

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

一个新的多项式实根分离算法

本文提出了分离多项式方程P(x)=0的实根的一个新的计算机代数算法,它解决了王湘浩教授在[1]中提出的用连分数变换分离有重根多项式的实根的问题.对于有重根的n次多项式P(x),该算法具有时间复杂性上界O(n~6L~3(|P|_0)),远远优于现有的解决同样问题的计算机代数算法的时间上界O(n~(10)+n~7L~3(|P|_0)).该算法已在计算机代数系统SAC-2上实现.上机实验的结果也初步证实了新算法的优越性.     

n 个规格化数的最优排序算法

<正> n 个实数的排序是最经常遇到的问题之一。目前常用的排序方法是“泡沫分类法”,用 ALGOL60书写,形式为for j:=n-1 step-1 until 1 dofor i:=1 until j doif A[i+1]相似文献