时间复杂度的几种计算方法

算法的时间复杂度是反映算法优劣的重要指标，是《数据结构》的重要理论基础，是学习和教学过程中贯穿始终的主要线索。但是由于概念的抽象和计算方法的繁琐，使算法时间复杂度成为最难理解和掌握的问题之一。在总结教学经验的基础上，该文提出几种常用的时间复杂度计算方法，使对该知识点的教学和学习变得系统和简单。

平均计算时间复杂度优化的动态粒子群优化算法

粒子群优化(PSO:Particle Swarm Optimization)算法已经被广泛地应用,其中包括大量实时性要求很高的领域,如宽带数字信号处理。传统PSO算法需要对大量粒子分别进行若干次迭代运算,这将导致该算法的平均计算时间复杂度较高,运算延时大,不能满足这种高实时性要求。因此,需要在不影响性能的前提下降低PSO算法的平均计算时间复杂度。提出了一种粒子数量可变的动态粒子群优化(DPSO:Dynamic PSO)算法,其核心是丢弃粒子判定条件,在迭代过程中,根据该条件动态地抛弃一些粒子,从而降低算法的平均计算时间复杂度。此外,在算法迭代过程中对粒子的个体极值进行变异,从而避免陷入局部最优解。实验和理论分析结果表明,在算法的平均计算时间复杂度方面,对于相同的优化结果,DPSO算法的平均计算时间复杂度比传统PSO算法降低了30%左右;在算法的性能方面,对于单峰值目标函数,DPSO算法与传统PSO算法的优化性能相当,而对于多峰值目标函数,DPSO算法的优化性能要优于传统PSO算法。

一种O（2．983^n）时间复杂度的最优联盟结构生成算法

首先,在有限整数集上建立有效拆分关系,在联盟集上建立有效二部分解关系,并设计了一种EOCS(effective optimal coalition structure)算法.该算法采用自底向上方式,只对具有有效二部分解关系的联盟进行二部分解来求联盟的优值,从而降低了二部分解的数量.随后,利用函数的克林闭包特性证明了EOCS算法的正确性,利用积分极限定理证明了EOCS算法时间复杂度的下界是O(2.818n),用时间序列分析方法求出了EOCS算法的上界是O(2.983n).最后,将EOCS算法与其他算法作了对比,指出无论联盟值满足何种概率分布,EOCS算法都能在O(2.983n)时间内找出最优联盟结构.Rothkopf提出的DP(dynamic programming)算法和Rahwan提出的IDP(improved dynamic programming)算法能够在O(3n)时间内求出最优联盟结构.所作的EOCS算法设计、正确性证明、时间复杂度的上下界分析都是对Rothkopf及Rahwan等人相关工作的改进和提高.

进化规划算法的时间复杂度分析

进化规划算法是求解连续优化问题的一类进化算法,是进化计算的一个重要分支.在进化规划算法的理论研究上,已有学者证明了其收敛性.然而,进化规划算法的时间复杂度分析是进化计算领域一大难题,目前相关的研究成果很少.基于吸收态Markov过程模型,以期望收敛时间作为研究进化规划算法时间复杂度的指标,提出了进化规划算法期望收敛时间的估算方法,并以此作为算法时间复杂度分析的理论依据.最后分析了Gauss变异进化规划算法的期望收敛时间,作为提出理论的应用举例.

遗传禁忌搜索算法收敛性和时间复杂度分析

遗传禁忌搜索算法多用于车辆路径优化、旅行商问题等,试验证明:融合遗传算法与禁忌搜索算法的混合算法相比单一算法的性能有较大提升,但缺少理论证明。本文阐述了遗传禁忌搜索算法的混合策略,从理论上对该算法的收敛性进行了证明,对时间复杂度进行了分析。应用马尔科夫链模型证明了遗传禁忌搜索算法是以概率1收敛到全局最优解的,并应用求解随机算法时间复杂度的方法,即求解算法的期望收敛时间,估算了该算法的时间复杂度,结果证明该算法的时间复杂度与所得解的多样性、问题规模以及遗传算法的种群数量有关。

一种时间复杂度为O(m)的无向超图核值求解算法

阐述了图核的全局信息在结点匹配中的应用,将图核理论扩展到超图上,提出了超图的核等相关概念,并给出了超图核值的形式化描述;分析了超图k水平p-核的构造性属性,给出了求解超图核值算法的基本步骤,进而讨论了降低时间复杂度的改进措施,提出了基于结点属性函数快速求解超图核值的算法框架;重点阐述了无向超图的改进压缩存储格式,将无向超图核值的求解算法从结点的度属性扩展到不同的结点属性函数,并给出了基于该存储格式的结点属性函数p5(v,U)核值求解算法,其时间复杂度为O(m),空间复杂度为O(n+m+z);最后,基于ISPD98测试基准的18组无向超图进行了结点的度和核值的求解对比实验,其数据对比表明:核值相比结点的度更能反映出结点在超图中的重要程度.

线要素化简算法的时间复杂度分析

线状要素是地图中数量最大、要素类型最多样的要素,其化简在地图自动综合中占据了重要的地位。目前对线状要素化简算法的改进、化简质量、化简精度等方面的研究较多,对线状要素化简算法的效率研究较少。此处是在兼顾化简质量的前提下研究算法效率,通过分析化简算法约束参数的特征,将线状要素化简算法分为6类,选取其中的几个典型算法,分析了其时间复杂度,并按照线状要素化简算法的时间复杂度将其分为线性算法和非线性算法两类,初步探讨了适合这两类算法的并行计算方法。

基于嵌入式平台的低时间复杂度目标跟踪算法

针对嵌入式平台往往算力受限的应用背景,提出了一种低时间复杂度的、适用于复杂场景的目标跟踪算法——CTSTC算法。算法由自适应更新的时空上下文目标跟踪环节和自适应更新的压缩感知目标辅助定位环节两部分构成,当时空上下文跟踪结果不可靠时,启动压缩感知目标辅助定位环节,如果辅助定位后的结果可靠,则采用辅助定位结果校正时空上下文跟踪环节。算法运行速度与时空上下文算法(STC)接近,I5CPU下测试可达每秒1577帧,远高于其他常用算法,是一种运算速度极高的目标跟踪算法,但算法在复杂环境下的鲁棒性却有所提升。使用OTB2013数据集进行测试,较STC算法,CTSTC精度提升12.8%,成功率提升27.5%。算法在以DM6437为核心的小型目标跟踪系统上进行测试,可以实现实时稳定跟踪。

不可能差分分析时间复杂度通用计算公式的改进

研究Boura等和Derbez分别提出的不可能差分分析时间复杂度计算公式,根据实际攻击过程优化密钥排除的步骤,给出不可能差分分析实际攻击的时间复杂度计算的改进公式,进而利用两个分组密码算法模型将改进后公式计算的实际结果分别与Boura等的公式和Derbez的公式的计算结果进行对比,结果表明Boura等的公式计算结果既可能高于优化公式的实际分析计算的结果,也可能低于优化公式的实际分析计算的结果,而在轮子密钥独立时改进后公式的实际计算结果是Derbez公式的计算结果的2-1.2倍。

算法及其时间复杂度可同步形式化推导的方法

对在长期的算法研究中提出的PAR方法和PAR平台引入时间谓词加以扩展,不仅可以形式化推导出顺序查找和二分查找问题的算法程序,而且这两个问题关于时间复杂度的递归方程式也可同步且自然地推导得到。这为开发并验证高效率的算法开辟了一条新途径。

基于分析法的算法时间复杂度的度量方法研究

在简要讨论简单算法和复杂算法通常所采用的传统的时间复杂度衡量方法的基础上,提出了一种基于分析法的时间复杂度衡量方法。该方法借助于分析二叉树特性,根据二叉树的特点分析算法中核心操作语句频度,与传统的方法相比,更简单,效率更高。

多播路由算法MPH的时间复杂度研究

多播通信是从一个源点同时向网络中的多个成员发送分组的通信服务 ,一个最小代价的多播路由算法是NP完全的 ,在时间敏感的应用中其运行时间是一个关键问题 .MPH(MinimumPathCostHeuristic)算法是一个著名的启发式最小代价多播路由算法 ,本文对该算法进行了理论分析和证明 ,并做了广泛的仿真实验 ,结果表明其时间复杂度是O(m2 n)而不是过去文献中所给出的O(m2 n +e) .

具有O(n)时间复杂度的分布式请求集生成算法

在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的。在基于松弛差集的相关原理上,引入了二次松弛差集的概念。经分析相关概念及定理,将原本"求差"的过程变为"求和"的过程;进而利用"求和"步骤间的递推关系,大大减少了求和步骤,使整个算法的时间复杂度控制在O(n)。与时间复杂度同为O(n2)的其他经典算法相比,生成的请求集长度仍保持在2槡n的数量级。

时间复杂度为O(N)的联接算法

本文提出基于Ｈａｓｈ位阵列结构的等值联接算法，它利用Ｈａｓｈ位阵列及链表来实现等值匹配查找，时间复杂度为Ｏ（Ｎ），而且实现此算法的结构比较简单，容易实现。普通联接算法的时间复杂度为Ｏ（Ｎ２）

S^3PR网多项式时间复杂度的化简算法

针对在一类S3PR网柔性制造系统Petri网模型N中的位置特殊资源不可能出现在网的严格极小信标之中的理论进行研究,对包含此类资源的网系统进行化简,分析了化简算法的时间性能,得出了该算法是多项式时间复杂度的结论,并推广了已有文献的结果.

算法的时间复杂度分析

算法的时间复杂度是衡量一个算法优劣的重要指标.在总结教学经验的基础上,提出了几种计算时间复杂度的方法.

用母函数理论分析递归算法的时间复杂度

对算法进行时间复杂度分析是算法分析与研究的重要内容,而对递归算法分析其时间复杂度时往往比较困难. 提出了用组合数学中的母函数与递推关系理论来分析一些特殊的递归算法的时间复杂度,并同时得出三个推论,在算法的 分析与研究方面具有一定的参考价值.

排序算法时间复杂度的研究

算法设计的好坏直接影响计算机的运行时间,计算机排序方法较多,时间复杂度差别较大.本文从理论上研究了线性排序(选择法、冒泡法、计数法)、比较排序、堆排序和快速排序等几种常用的排序算法的时间复杂度.

利用双堆栈降低时间复杂度的新算法

分析了由树的前序序列和中序序列建树问题的递归算法的最坏时间复杂度和平均时间复杂度，以及利用哈希表改进查找得到的算法的时间复杂度；提出了利用两个堆栈构造的新算法，并证明其最坏时间复杂度与平均时间复杂度均为Ｏ（ｎ）．