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

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

简单无向图中H回路搜索的避圈算法

本文提出一个在简单无向图中搜索H回路的新算法,我们称之为避圈算法。我们分析的算法对于n阶简单无向图的时间复杂性亦为O(n~2·2~n),但VAX机上的程序实现和对2000例以上的64阶图的运行表明。只要G是H图,算法就可以立即找到一条H回路。而其它算法对于同样图例在10小时的连续运行时间里未能找到一条H回路。据此,我们猜测,本算法(或其改进)的时空复杂性远比我们分析的保守结果好得多,或者至少本算法也象著名的单纯形算法那样。理论复杂性很高但实际复杂性很低,因为很少出现最坏情况。本文是[1]中结论的直接结果。     

在Z(p~k)中计算逆元的逐位消除算法

讨论在模n=pk(p是素数)剩余类环R中计算逆元的算法。本文引入可逆元的阶的概念,在对阶的性质进行讨论的基础上,提出计算逆元的逐位消除算法。算法的时间复杂度为O(k2)=O((logpn)2)。     

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

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

相似文献   

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

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

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

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

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

本文提出适用于多维灰度图象的λ-连通分割算法,其计算时间为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(1.380np(n)),]其中[p(n)]表示问题规模数[n]的多项式函数。运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂度由原来的[O(1.380np(n))]降为[O(1.325np(n))]。研究结果表明运用加权分治技术能够得到较为精确的时间复杂度。     

在SIMD机器上实现的双调选择算法

(m,n)选择问题在多处理器系统上的并行求解是一个具有实际意义的研究课题。单指令多数据流(SIMD)机器是目前一种较为成熟和流行的并行处理系统。本文给出了在立方连接、洗牌交换连接和网孔连接三种典型SIMD机器模型上并行求解(m,n)选择问题的双调选择算法,它们所需的数据比较交换次数均为O(logn logm),数据移动次数分别为O(logn·logm)、O(log~2n)和O(n)~(1/2)。     

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

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

r-循环矩阵开平方的两个快速算法

本文利用快速富里叶变换(FFT)和矩阵分块逐次降阶的方法，给出了两种n阶r—循环矩阵开平方的快速算法，其计算复杂性均为O(nlog2n)。     

基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

一种加群Z上离散对数问题的DNA计算算法

加群Zp+上离散对数问题在公钥密码系统分析中具有非常广泛的应用。研究一种加群Zp+上离散对数问题的DNA计算算法。算法主要由解空间生成器、并行乘法器、并行加法器、解转换器及解搜索器组成。其中解空间生成器借鉴传统计算机中3表算法的思想,将解空间的生成分为3个部分来完成,极大减少了非法解的搜索空间。本算法的生物操作时间复杂度为O(k2),需要O(1)个试管数、O(2k)条DNA链,最长DNA链长为O(k2)(其中k为加群上离散对数问题群阶p的二进制编码位数)。最后,通过DNA计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性。     

一种构建最优二叉查找树的贪心算法

分析最优二叉查找树与哈夫曼树的异同,提出解决最优二叉查找树问题的贪心算法,证明算法的正确性,并用C++程序设计语言编码实现。该算法时间复杂度为O(n2),空间复杂度为O(n),实现了空间复杂度阶的突破。实验结果表明:所提出的贪心算法的效率明显优于动态规划算法。     

最长模式子序列问题的算法分析

最长模式子序列问题在生物信息学中有重要的应用.本文首次提出求a=aoa1…an-1∈ωn的最长σ模式子序列的O(n2)时间算法,并对|σ|≤2的情形推广了RSK算法和标准Young表,对算法作了改进,得到了当|σ|=1时的O(nlogk)时间算法和当|σ|=2时的O(n)时间算法.     

多队列快速排序

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

Fast Parallel Molecular Algorithm for Solving the Discrete Logarithm Problem over Group on Zp+ DNA-based Computing

加群Zp+上离散对数问题在公钥密码系统分析中具有非常广泛的应用.研究一种加群Zp+上离散对数问题的DNA计算算法.算法主要由解空间生成器、并行乘法器、并行加法器、解转换器及解搜索器组成.其中解空间生成器借鉴传统计算机中3表算法的思想,将解空间的生成分为3个部分来完成,极大减少了非法解的搜索空间.本算法的生物操作时间复杂度为O(k2),需要O(1)个试管数、O(2k)条DNA链,最长DNA链长为O(k2)(其中k为加群上离散对数问题群阶p的二进制编码位数).最后,通过DNA计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性.     

Neville编解码问题的线性时间算法

讨论标号树的Neville编码的编解码算法.文献中常见的第2种Neville编解码算法需要O(n log n)时间.近期研究文献指出至今尚未找到第2种Neville编解码的线性时间算法.本文对第2种Neville编解码问题的本质特征进行较深入的分析,从简单算法出发,逐步简化,得到一个非常简单实用的O(n)时间Neville编解码算法.本文采用的解决问题的方法也具有一定的技巧,可供解决类似问题时借鉴.     

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

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

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

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