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符号也是

最近更新

云南省实验幼儿园幼升小衔接班自我检测试题-含.. 3页

云南省2020版保育员三级业务水平考试试题试题.. 11页

云南省2019版保育员五级业务能力考试试题试题.. 12页

云南省2018版保育员五级业务技能考试试题试题.. 12页

乡镇工业经济发展一年总结与乡镇工业经济发展.. 6页

8月人事部个人工作计划与8月份党支部工作计划.. 6页

2020版幼儿园保育员高级考试试题(II卷)-(附解.. 10页

管理信息系统电子政务 19页

新型骨瘤治疗药物筛选-全面剖析 25页

市政道路石材供应运输合同3篇 51页

牙膏中活性成分对敏感牙齿的脱敏效果研究-全面.. 30页

工业园区居间协议模板3篇 51页

展览馆装修工装合同协议书3篇 50页

展会垃圾运输临时协议3篇 53页

宾馆装修挂靠合同样本3篇 49页

家电卖场装修3篇 53页

家居超市装修项目合同3篇 53页

简爱性格分析英文版 12页

简单期权的离散模型定价 37页

高考作文模板应用与拓展-全面剖析 26页

2025年吕梁职业技术学院单招职业适应性测试题.. 74页

高清地图中国31省市区最全河流水系分布地图建.. 25页

2023年北京市事业单位统考真题及答案 11页

2025届高考模拟作文“时间管理”升格导写 5页

剑桥雅思原版真题4 114页

《于宏杰-到底神要的是什么呢》 5页

毒物分析-第七章 PPT课件 42页

黄庭禅—心即是气.pdf 23页

《各各他的十字架》宾路易师母 47页

500KV电压互感器使用说明 30页