1 / 8
文档名称:

时间复杂度的计算.doc

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

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

分享

预览

时间复杂度的计算.doc

上传人:水中望月 2019/3/20 文件大小:24 KB

下载得到文件列表

时间复杂度的计算.doc

相关文档

文档介绍

文档介绍:时间复杂度计算学习数据结构时,觉得时间复杂度计算很复杂,怎么也看不懂,差不多三年之后,还是不懂,马上就要找工作了,赶紧恶补一下吧:首先了解一下几个概念。一个是时间复杂度,一个是渐近时间复杂度。前者是某个算法的时间耗费,它是该算法所求解问题规模n的函数,而后者是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。当我们评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度,因此,在算法分析时,往往对两者不予区分,经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度,其中的f(n)一般是算法中频度最大的语句频度。此外,算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。常见的时间复杂度,按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。(n)来表示,对于一个查找算法,如下:intseqsearch(inta[],constintn,constintx){inti=0;for(;a[i]!=x&&i<n;i++);if(i==n)return-1;elsereturni;}这个程序是将输入的数值顺序地与数组中地元素逐个比较,找出与之相等地元素。在第一个元素就找到需要比较一次,在第二个元素找到需要比较2次,……,在第n个元素找到需要比较n次。对于有n个元素的数组,如果每个元素被找到的概率相等,那么查找成功的平均比较次数为:f(n)=1/n(n+(n-1)+(n-2)+...+1)=(n+1)/2=O(n)这就是传说中的大O函数的原始定义。用大O来表述要全面分析一个算法,需要考虑算法在最坏和最好的情况下的时间代价,和在平均情况下的时间代价。对于最坏情况,采用大O表示法的一般提法(注意,这里用的是“一般提法”)是:当且仅当存在正整数c和n0,使得T(n)<=c*f(n)对于所有的n>=n0都成立。则称该算法的渐进时间复杂度为T(n)=O(f(n))。这个应该是高等数学里面的第一章极限里面的知识。这里f(n)=(n+1)/2,那么c*f(n)也就是一个一次函数。就是在图象上看就是如果这个函数在c*f(n)的下面,就是复杂度为T(n)=O(f(n))。对于对数级,我们用大O记法记为O(log2N)就可以了。规则1)加法规则T(n,m)=T1(n)+T2(n)=O(max(f(n),g(m))2)乘法规则T(n,m)=T1(n)*T2(m)=O(f(n)*g(m))3)一个特例在大O表示法里面有一个特例,如果T1(n)=O©,c是一个与n无关的任意常数,T2(n)=O(f(n))则有T(n)=T1(n)*T2(n)=O(c*f(n))=O(f(n)).也就是说,在大O表示法中,任何非0正常数都属于同一数量级,记为O(1)。4)一个经验规则有如下复杂度关系c<log2N<n<n*Log2N<n^2<n^3<2^n<3^n<n!其中c是一个常量,如果一个算法的复杂度为c、log2N、n、n*log2N,那么这个算法时间效率比较高,如果是2^n,3^n,n!,那么稍微大一些的n

最近更新

2025年脑梗溶栓疗法精要解读 12页

2025年4分钟导游词 4页

2025年肝细胞癌症状与治疗全解析 76页

2025年肋骨骨折康复护理要点解读 28页

北部湾经济区海洋运输业发展趋势分析 2页

2025年2025新课标I卷高考作文 46页

2025年----英语六级 6页

北京前门商业区道路交通问题分析 2页

包钢高炉渣场铁路的技术改造及管理 2页

2025年皮肤CT技术在医疗诊断中的应用解析 14页

加快推进房地产企业住宅产业化进程的思考 2页

加强技术基础管理 稳步提高产品质量 2页

加入WTO对我国资本市场的影响初探 2页

制氢装置中变气换热流程运行分析 2页

利用闪烁法测量定向剂量当量的实验研究 2页

利用电厂液态渣作混凝土细骨料的研究 2页

利用担子菌混合发酵酿制酱油的研究 2页

2025年截瘫人士高效转移技巧探讨 10页

企业基本业务的会计核算 154页

创新测井培训方法 强化人才队伍素质 2页

刍议产品寿命周期研究在销售量预测中的应用 2页

分析公路桥梁施工中裂缝的成因及防治 2页

2025年均衡饮食营养搭配攻略 20页

凝结水泵轴承振动超标分析及处理方法 2页

减压下正丁醇[1]—甲苯[2]系汽液平衡的研究 2页

2025年儿童腺样体扁桃体切除术后康复指南 22页

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

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

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

CNAS-EL-03《检测和校准实验室认可能力范围表.. 10页