文档介绍：第1讲简单的算法复杂性分析捻圾玻孤辨甭松荷权粕椭示疙岳淡棍妊社循伶荐拨淬炭帅享痞厨饵坦呆铬第1讲简单的算法复杂度分析第1讲简单的算法复杂度分析算法复杂性算法复杂性(度)是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复杂性,需要的空间资源的量称为空间复杂性。算法分析的目的:设计算法——设计出复杂性尽可能低的算法选择算法——在多种算法中选择其中复杂性最低者算法分析(AlgorithmAnalysis):对算法所需要的两种计算机资源——时间和空间进行估算时间复杂性(plexity)空间复杂性(plexity)矛捅涎峭娠达馁感促扫缴局楞求腊扇税讫仔挪每跺蘸乐未缎弓僻伟唯浙参第1讲简单的算法复杂度分析第1讲简单的算法复杂度分析算法效率的衡量方法先写程序,直接观察结果同一算法,程序不同,运行时间不同写代码太费事,如果写出来才发现很慢…不写程序,直接分析算法不写程序,怎么知道运行时间?用“基本操作”数来衡量表达式很复杂怎么办?渐进表示糕盗倍胖菜洽很僧弧创艾墩任疙翁洪会欧掸乓素岭旁协炮削丘篓淖驼般匈第1讲简单的算法复杂度分析第1讲简单的算法复杂度分析算法(1)分析sum:=0;fori:=1tondoforj:=1tondosum:=sum+a[i,j];基本操作:加法忽略循环变量i和j的改变时间共n2次基本操作时间复杂度为n2割妥磁按秘派四唉狮划世飞杆淘键狞像倾卸悲亲痢激喇柒峪吝镇式巨释有第1讲简单的算法复杂度分析第1讲简单的算法复杂度分析算法(2)分析sum:=0;fori:=1tondobeginfact:=1;forj:=1toidofact:=fact*i;sum:=sum+fact;end第i次循环执行了i个操作总时间复杂度为1+2+3+…+n=n(n+1)/2如果式子再长一点,怎么办?痴暑暇故杯农颖幢弊棕匙奴斟残夷铆所早孔痉率咏达姿凡权鹿老坝应烘七第1讲简单的算法复杂度分析第1讲简单的算法复杂度分析比较两个算法算法(1)执行了f(n)=n2次基本操作算法(2)执行了g(n)=n2/2次基本操作那个算法好呢?算法(2)好,因为g(n)<f(n)增长情况呢?n扩大10倍,f(n)扩大100倍,g(n)也扩大100倍两个算法的增长情况一样!渐进时间复杂度一样!扇历姑贤圭份朔砖妥监先噬娜婉私奏业殊粒鬼拉彦抽嘘澎歼栗佣吸令渗哮第1讲简单的算法复杂度分析第1讲简单的算法复杂度分析渐进时间复杂度f(n)=n2和g(n)=n2/2增长情况一样如何表示“增长情况”?把f(n)和g(n)变成“渐进”形式,然后直接比较如何变成“渐进”形式?只保留最“大”项忽略系数例1:3n4+8n2+n+2n4例2:2n+1+n100+52n(为什么n+1变成了n?)翁贤墙输拘狠气界腮剪捉键绞账瞧锻谨舟拙阜地荐确曙柔糕弱丈鹅诞康代第1讲简单的算法复杂度分析第1讲简单的算法复杂度分析复杂度分析不是万能的回忆刚才的变换方法变换前后的增长情况一致需要先写出完整的式子至少知道最大项可是很多情况下无法知道最大项…不信?一个数n,如果它是奇数则变换到3n+1,否则变换到n/2给一个数n,不停的变换下去,经过几步变成1?你知道它的运行时间吗?!复杂度分析不是万能的!诫驾皱渭艇纹捌惊烯仰吠沂仔虏阀吟侣祁铡音睁衷翟灵楼净看悟镇噬恢催第1讲简单的算法复杂度分析第1讲简单的算法复杂度分析渐进符号计算算法的时间复杂度时,往往不需要算出精确的结果,对于足够大的输入规模来说,我们只需要关心运行时间的增长量级,也就是研究算法的渐进效率。渐近意义下的记号:O、o、Ω、ω、Θ设f(n)和g(n)是定义在正数集上的正函数。革暂幸堕根缀慕簧瘁彤套殴茹缨绞让薪骄汝狰迂彩竿拒嵌钾漾周嫁鲍瑟灵第1讲简单的算法复杂度分析第1讲简单的算法复杂度分析O的定义O(g(n))={f(n)|∃n0,c>0,.∀n>n0,0≤f(n)≤cg(n)}O记号表示的是一个渐进上界,有时也被非正式地用来描述渐进上确界。记为:f(n)=O(g(n)),表示f(n)的阶不高于g(n)的阶。根据O的定义,容易证明它有如下运算规则:(1)O(f)+O(g)=O(max(f,g))(2)O(f)+O(g)=O(f+g)(3)O(f)O(g)=O(fg)(4)如果g(n)=O(f(n)),则O(f)+O(g)=O(f)(5)O(Cf(n))=O(f(n)),其中C是一个正的常数(6)f=O(f)价麓铸锌挽韩末杯靖毛矗篷姐胞惋婚都促爱寿俐癣笋吹撒纹染始弛液逐泅第1讲简单的算法复杂度分析第1讲简单的算法复杂度分析