检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

间接交互模式的时间复杂度分析及应用

北京工业大学学报 2013年第1期39卷 81-86页

作者：彭淑芬何泾沙高枫北京工业大学计算机学院北京100124 北京工业大学软件学院北京100124

为了定量分析间接交互模式的时间复杂度,提出了3种基础间接交互模式的模糊时间Petri网模型及其模糊时间复杂度.整体交互模式的发起者到接收者的可达树搜索算法设计了包含间接交互模式的整体交互模式的搜索算法,同时评估了整体交互模式... 详细信息

为了定量分析间接交互模式的时间复杂度,提出了3种基础间接交互模式的模糊时间Petri网模型及其模糊时间复杂度.整体交互模式的发起者到接收者的可达树搜索算法设计了包含间接交互模式的整体交互模式的搜索算法,同时评估了整体交互模式的模糊时间复杂度.并以一个实例分析了间接交互模式在网络交互模式建立中的应用.这种方法能快速评估整体交互模式的时间复杂度,为整体交互模式的筛选提供准确的数据.

关键词：交互模式模糊时间 Petri网时间复杂度

在线全文

学校读者我要写书评

暂无评论

辨识阵构造方法更精确的时间复杂度模型

控制工程 2018年第9期25卷 1771-1776页

作者：胡霞费鹏杜卫锋苏州工业职业技术学院软件与服务外包学院江苏苏州215104 苏州市创采软件有限公司江苏苏州215128 嘉兴学院数理与信息工程学院浙江嘉兴314001

属性约简是粗糙集理论的核心研究内容之一,基于辨识阵的方法可以获得所有的约简,该方法的1个关键步骤是构造辨识阵,如何降低构造辨识阵的代价以及估计构造辨识阵的时间复杂度,具有重要的理论与实用价值。通过先对协调决策表,再对不协调... 详细信息

属性约简是粗糙集理论的核心研究内容之一,基于辨识阵的方法可以获得所有的约简,该方法的1个关键步骤是构造辨识阵,如何降低构造辨识阵的代价以及估计构造辨识阵的时间复杂度,具有重要的理论与实用价值。通过先对协调决策表,再对不协调决策表的深入研究和分析,给出了辨识阵构造方法时间复杂度更精确的上界模型。通过给出1个简单的不协调决策表实例,对该实例进行计算,并对计算结果加以说明;然后对若干中等规模的数据集进行了仿真测试,该模型给出的理论估计值与程序得到的实际测试值均十分接近,相对误差基本上都在3%之内,表明了该模型的有效性和正确性,为估计构造辨识阵的时间复杂度提供了更精确的理论模型。

关键词：粗糙集属性约简辨识阵时间复杂度

在线全文

学校读者我要写书评

暂无评论

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

电子元器件与信息技术 2023年第6期7卷 127-130+134页

作者：周士红广东培正学院

时间复杂度是衡量算法效率的一个重要指标，贯穿了整个数据结构课程的教学和学习过程。但因为时间复杂度的概念比较抽象，并且对于某些算法来说，其时间复杂度的计算过程也比较烦琐，所以是一个教学难点，对于学生来说也是一个学习难点... 详细信息

时间复杂度是衡量算法效率的一个重要指标，贯穿了整个数据结构课程的教学和学习过程。但因为时间复杂度的概念比较抽象，并且对于某些算法来说，其时间复杂度的计算过程也比较烦琐，所以是一个教学难点，对于学生来说也是一个学习难点。本文在总结几年数据结构教学经验的基础上，结合学生的学习特点以及学习过程中遇到的实际问题，系统地阐述了几种算法时间复杂度的分析方法，使得算法时间复杂度的分析变得更清晰，帮助学生更好地掌握相关知识。

关键词：算法时间复杂度数据结构

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

演化算法在连续搜索空间上的时间复杂度分析

演化算法在连续搜索空间上的时间复杂度分析

作者：姜武中国科学技术大学

学位级别：硕士

自提出以来,演化算法就受到学术界的持续关注,同时在实际工程领域中得到广泛的应用。作为基于种群的随机优化算法,演化算法不仅能够克服传统优化算法的许多缺点,例如依赖于目标函数的梯度或者海森矩阵、在多峰问题上性能不好、对初始点... 详细信息

自提出以来,演化算法就受到学术界的持续关注,同时在实际工程领域中得到广泛的应用。作为基于种群的随机优化算法,演化算法不仅能够克服传统优化算法的许多缺点,例如依赖于目标函数的梯度或者海森矩阵、在多峰问题上性能不好、对初始点的选取敏感等等,并且在解决实际问题时有着非常好的表现。然而,演化算法运行过程的随机性,也使得对它的时间复杂度的研究变得困难,进而成为限制其进一步发展的瓶颈。近二十年来,对演化算法的时间复杂度的研究也逐渐成为该领域内的研究热点。从早期的定性分析过渡到现在的定量分析,该领域中涌现出许多优秀的理论成果。然而,现有的工作主要集中在对离散型演化算法的分析。连续优化问题是实际工程中更常见的一类问题,但是针对它的时间复杂性研究仍然十分稀少。因此,我们将重点分析连续型演化算法的时间复杂度,以弥补当前研究现状的不足。本文的主要贡献可归纳为以下几点:1.总结了连续型演化算法的理论分析领域的相关工作。根据成果的类型,将现有的理论成果分为局部性态分析和渐进分析。渐进分析的理论成果,按照所分析的算法类型又可以分为基于个体的和基于种群的。2.提升了使用超球体内均匀分布变异算子的演化算法的下界。变异算子是演化算法中的重要部件之一,它表示算法的搜索方向,并且会直接影响到算法的时间复杂度。在本文中,我们考虑一种常见的变异算子——均匀分布变异算子,并将其下界从目前最优的下界Ω(n)提升至Ω(ecn),即从多项式时间下界提升至指数级时间下界。3.分析了 1/5规则在超球体内均匀分布变异算子上的效用。1/5规则是连续型演化算法中用来调整变异强度的一个常用的启发式策略。在本文中,我们证明了使用1/5规则可以将算法的时间复杂度从Ω(ecn)降为O(n),即从指数级时间降为多项式时间。

关键词：连续优化演化算法时间复杂度 1/5规则

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

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

河南理工大学学报（自然科学版） 2018年第4期37卷 118-122页

作者：牟乃夏徐玉静李洁张灵先山东科技大学测绘科学与工程学院山东青岛266590 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室北京100101

遗传禁忌搜索算法多用于车辆路径优化、旅行商问题等,试验证明:融合遗传算法与禁忌搜索算法的混合算法相比单一算法的性能有较大提升,但缺少理论证明。本文阐述了遗传禁忌搜索算法的混合策略,从理论上对该算法的收敛性进行了证明,对时... 详细信息

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

关键词：遗传算法禁忌搜索算法收敛性时间复杂度马尔科夫链模型

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

在线全文

学校读者我要写书评

暂无评论

小型微型计算机系统 2013年第11期34卷 2568-2573页

作者：冷明孙凌宇边计年马昱春井冈山大学计算机科学系江西吉安343009 清华大学计算机科学与技术系北京100084

阐述了图核的全局信息在结点匹配中的应用,将图核理论扩展到超图上,提出了超图的核等相关概念,并给出了超图核值的形式化描述;分析了超图k水平p-核的构造性属性,给出了求解超图核值算法的基本步骤,进而讨论了降低时间复杂度的改进措施,... 详细信息

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

关键词：无向超图核值时间复杂度算法

在线全文

学校读者我要写书评

暂无评论

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

计算机研究与发展 2008年第11期45卷 1850-1857页

作者：黄翰郝志峰秦勇华南理工大学软件学院广州510006 华南理工大学计算机科学与工程学院广州510006 茂名学院信息与网络中心广东茂名525000

进化规划算法是求解连续优化问题的一类进化算法,是进化计算的一个重要分支.在进化规划算法的理论研究上,已有学者证明了其收敛性.然而,进化规划算法的时间复杂度分析是进化计算领域一大难题,目前相关的研究成果很少.基于吸收态Markov... 详细信息

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

关键词：进化计算进化规划算法时间复杂度期望收敛时间 Gauss变异

在线全文

学校读者我要写书评

暂无评论

低时间复杂度的快速KNN算法研究及其应用

低时间复杂度的快速KNN算法研究及其应用

作者：余阳山东科技大学

学位级别：硕士

KNN算法是一种非常经典的划分类别的算法,主要解决未知属性样本分类问题,算法在分类过程中,需要计算未知属性样本与每个已知属性样本的距离,因此在海量高维数据的应用中,传统KNN算法计算复杂度较高的缺点受到严重挑战,针对该缺点本文进... 详细信息

KNN算法是一种非常经典的划分类别的算法,主要解决未知属性样本分类问题,算法在分类过程中,需要计算未知属性样本与每个已知属性样本的距离,因此在海量高维数据的应用中,传统KNN算法计算复杂度较高的缺点受到严重挑战,针对该缺点本文进行了研究。基于距离的离群数据检测算法是常用的离群数据检测算法之一,但该算法在海量高维数据面前计算复杂度较高,针对这个缺点本文也进行了研究。论文主要工作如下:第一,针对传统KNN算法在海量高维数据面前分类效率较低,提出低时间复杂度的快速KNN算法。该算法与传统KNN算法不同之处在于:首先,从未知属性样本集中任意选择一部分样本进行分类,然后,从剩余未知属性样本中任选一个样本,计算其与所有已分类样本的距离,最后,以距离其最近的已分类样本为圆心,以两者距离的两倍再加上最近已分类样本k近邻中距离最远样本的距离为半径,作超球体。超球体外的样本则无需与该待分类样本计算距离,从而减少计算量,达到降低计算复杂度的效果。实验结果显示,提出的算法分类效率更高。第二,将基于类重心的KNN算法与低时间复杂度的快速KNN算法相结合,得到基于类重心的快速KNN算法,该算法步骤与低时间复杂度的快速KNN算法基本一致,不同之处在于算法的k值全部取1,并用均值作为各个类的类重心,则待分类样本只需与类重心计算距离,其余步骤与低时间复杂度的快速KNN算法一致。实验结果显示,基于类重心的快速KNN算法的效率比传统基于类重心的KNN算法效率更高。第三,将传统基于距离的离群数据检测算法进行改进,提出基于距离的快速离群数据检测算法。传统算法需要计算待测样本与所有样本的距离,而提出的算法从第二个待测样本开始（第一个任意选择的样本,与传统算法计算方法一致）,无需与其他所有样本计算距离,只需与以第一个已测样本为圆心,以待测样本与圆心的距离加上事先给定的邻域半径为半径的超球体内的样本计算距离。当待测样本与圆心的距离大于给定的邻域半径时,此时建立空心超球体,空心部分的半径是待测样本与圆心的距离减去给定的邻域半径,超球体外和空心部分的样本则无需与待测样本计算距离,从而达到降低算法计算复杂度的效果。实验结果显示提出的算法的检测效率比传统算法的检测效率更高。第四,利用低时间复杂度的快速KNN算法思想,提出一种低时间复杂度的快速KNN离群数据检测算法,该算法与传统基于距离的离群数据检测算法不同之处在于:传统算法是让检测样本的邻域半径都为d的情况下,用检测样本的邻居数量与给定的邻域参数ε进行比较,而提出的算法则是让检测样本邻居数量都为ε的情况下,用事先给定的邻域半径d与检测样本邻域内最远样本的距离进行比较,实验结果显示,提出的算法的检测效率比传统算法的检测效率更高。最后,总结了论文的研究内容,并提出研究领域的不足之处,以及可继续研究的方向。

关键词： KNN算法快速KNN算法离群数据空心超球体时间复杂度

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

点群选取与化简算法时间复杂度研究

南京师大学报（自然科学版） 2012年第1期35卷 111-116页

作者：于艳平沈婕尚在颖南京师范大学地理科学学院江苏南京210046 虚拟地理环境教育部重点实验室江苏南京210046 地理信息科学江苏省重点实验室江苏南京210046

点群目标作为地图的基本要素,是普通地图及专题表达的重要内容.近年来,随着网络地图与移动地图的发展,兴趣点已成为最为重要的表达要素,其数据生产、更新与表达逐渐成为研究热点.针对点群要素的综合,选取与化简是两种常用的操作.传统的... 详细信息

点群目标作为地图的基本要素,是普通地图及专题表达的重要内容.近年来,随着网络地图与移动地图的发展,兴趣点已成为最为重要的表达要素,其数据生产、更新与表达逐渐成为研究热点.针对点群要素的综合,选取与化简是两种常用的操作.传统的点群选取与化简算法主要是针对地图的自动生产,因此较侧重于点综合的质量,而随着GIS数据实时表达需求的增长和LBS服务的发展,对点综合算法的效率提出了更高的要求.本文在调研了常见点群选取与化简算法的基础上,按照实现原理的不同将算法分类,每一类中分别选取了一种具有代表性的算法,对其时间复杂度进行分析,并初步探讨了这些算法移植到并行计算环境下的可行性.这一研究将为点群选取与化简算法在网络地图及应急地图服务的应用与拓展奠定基础.

关键词：点群要素选取化简算法时间复杂度