1 / 7
文档名称:

2020年算法的时间复杂度和空间复杂度-总结.doc

格式:doc   大小:138KB   页数:7页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

2020年算法的时间复杂度和空间复杂度-总结.doc

上传人:梅花书斋 2020/2/22 文件大小:138 KB

下载得到文件列表

2020年算法的时间复杂度和空间复杂度-总结.doc

文档介绍

文档介绍:算法的时间复杂度和空间复杂度-总结       通常,对于一个给定的算法,我们要做两项分析。第一是从数学上证明算法的正确性,这一步主要用到形式化证明的方法及相关推理模式,如循环不变式、数学归纳法等。而在证明算法是正确的基础上,第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。因此,作为程序员,掌握基本的算法时间复杂度分析方法是很有必要的。      算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。一、事后统计的方法        这种方法可行,但不是一个好的方法。该方法有两个缺陷:一是要想对设计的算法的运行性能进行评测,必须先依据算法编制相应的程序并实际运行;二是所得时间的统计量依赖于计算机的硬件、软件等环境因素,有时容易掩盖算法本身的优势。二、事前分析估算的方法       因事后统计方法更多的依赖于计算机的硬件、软件等环境因素,有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。在编写程序前,依据统计方法对算法进行估算。一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素:      (1). 算法采用的策略、方法;(2). 编译产生的代码质量;(3). 问题的输入规模;(4).  机器执行指令的速度。     一个算法是由控制结构(顺序、分支和循环3种)和原操作(指固有数据类型的操作)构成的,则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法,通常的做法是,从算法中选取一种对于所研究的问题(或算法类型)来说是基本操作的原操作,以该基本操作的重复执行的次数作为算法的时间量度。1、时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就能够了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。(2)时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。       另外,上面公式中用到的Landau符号其实是由德国数论学家保罗·巴赫曼(PaulBachmann)在其1892年的著作《解析数论》首先引入,由另一位德国数论学家艾德蒙·朗道(EdmundLandau)推广。Landau符号的作用在于用简单的函数来描述复杂函数行为,给出一个上或下(确)界。在计算算法复杂度时一般只用到大O符号,Landau符号体系中的小o符号、Θ符号等等比较不常用。这里的O,最初是用大写希腊字母,但现在都用大写英语字母O;小o符号也是

最近更新

2025年核医学风险控制与安全管理策略 37页

关于云南经济战略研究中几个问题的思考 2页

关于主变经济运行系统若干问题的探讨 2页

展览行业市场发展机会分析 30页

关于两个矩阵之和的性质的进一步讨论 2页

《银行存款的清查说》 21页

《药用植物学》 81页

《药典基本知识》 54页

关于Boltzmann H定理的讨论 2页

关于35CrNiMoV钢的蝶状马氏体的研究 2页

2025年ICU病房感染防控策略与实践 30页

2025年慢性消化功能紊乱症状解析 27页

2025年情绪管理与心理健康实操指南 57页

六层大开间组合砌体房屋试验的抗震承载力分析.. 2页

2025年急性呼吸窘迫综合征合并气胸治疗策略 86页

公司内部控制有效性的实证分析 2页

八种沙鼠亚科和田鼠亚科啮齿动物阴茎的比较研.. 2页

八二八毛皮脱脂剂的研制和应用 2页

2025年幽门螺杆菌防治宝典患者必读指南 25页

全省锅炉、高压容器手工焊接技术表演赛 2页

全液压自动猫道翻板机构动力学仿真分析 2页

全息图制作方法和通过该方法制作的全息图 2页

全国高校物价教学研究会第四届年会在呼和浩特.. 2页

全国隐蔽油气藏勘探学术讨论会在江苏省无锡胜.. 2页

全国第四届冷弯型钢技术交流会在京召开 2页

2025年子宫肌瘤患者必读的全方位指南 17页

2025年妇产超声检查攻略 47页

(完整版)小学生必背古诗词80首 2页

计算机专业毕业论文3000字 6页

市政道路监理细则[1] 26页