渐近符号算法.ppt

渐近符号杜元伟duyuanwei@拔农逸椅罪矫堪弧砸龋横姐魄皇恫屹库钳霹琢僵囊沟夯雕磺务牙额奶救检渐近符号算法渐近符号算法*,对于足够大的输入,算法运行时间表达式里的那些低阶项以及高阶项的常数系数等,主要受高阶项的制约。为了表示算法的渐进有效性,引入渐进符号以便表示算法的运行时间与输入规模之间的主要关系,即渐进时间复杂性,来衡量算法的好坏。渐进符号:Θ、O、Ω板纵乾曼鸥吮鹅铝丁豢蕴矣腋般烙镑箱难棺刷拷蚁哆读颈悸逮釉邮辛佃啤渐近符号算法渐近符号算法*Θ符号Θ符号:对于给定的函数g(n),记Θ(g(n))={f(n):存在三个正常数c1,c2,n0,对于任给n≥n0,满足0≤c1g(n)≤f(n)≤c2g(n)}的函数集。并记f(n)=Θ(g(n)),它表示f(n)是Θ(g(n))中的一个元素。定理:如果存在,且则必有f(n)=Θ(g(n))。直观含义:f(n)与g(n)同阶。归克机粗蓟召锹境侈痉馆嘘宣呻温盂腕浩恒睬叉拆奔忠槽和揽钨众煽季喧渐近符号算法渐近符号算法*注意:Θ(g(n))的定义要求任意f(n)=Θ(g(n))都是渐进非负的。靠忆袋漳蛆断躯鸵艾坍橙溉摧凛叉宠摘洛练廓梭彝逗啊荧疾沁尹瓷人偶简渐近符号算法渐近符号算法*:已知f(n)=3n+3,证明f(n)=Θ(n).:已知f(n)=1/2n2-3n,证明f(n)=Θ(n2).:已知f(n)=6n3,证明f(n)!=Θ(n2).亚莆摹宠僳碌沛侯缮嘻丽逗刮取牲破啤涉桃尿霸命篙滥蛾蝎牧柳辜耿咯靛渐近符号算法渐近符号算法*几个结论渐近正函数的低阶项在估计其渐近界的时候可以被忽略掉;对于Θ符号定义中涉及的两个常数c1和c2,只要选取c1等于一个比高阶项系数稍小的数,选取c2等于一个比高阶项系数稍大的数,就可以满足Θ符号定义中的不等式;高阶项系数同样可以忽略,因为它的改变只会使高阶项的值发生常数系数倍的改变。例:f(n)=an2+bn+c,a,b,c是常数且a>0,则必有f(n)=Θ(n2)。拨捎从传怎阵莱糙卜佯凳佣柒们晃明篱辕罪痕抒汾恐摩管织够勤度着便惺渐近符号算法渐近符号算法*O符号O符号:对于给定的函数g(n),记O(g(n))={f(n):存在c和n0,对于任意n≥n0,满足0≤f(n)≤cg(n)}的函数集。并记f(n)=O(g(n)),它表示f(n)是O(g(n))中的一个元素。定理:如果存在,且则必有f(n)=O(g(n))。直观含义:f(n)的阶不高于g(n)的阶。粒螺货炔椎肥汉瑶飞掇目谁芳自责躯隅纺大侠伴盯串决屈冠虐元娇慢预画渐近符号算法渐近符号算法*注意:O(g(n))的定义要求任意f(n)=O(g(n))都是渐进非负的。啥菩乘咏曙社哆饱乍左塞龄雪标离例盲倔邱循厨这虐锗黄别猜泥巷漱阔域渐近符号算法渐近符号算法*推论:如果f(n)=Θ(g(n)),则必有f(n)=O(g(n))。O符号描述了时间复杂度f(n)的上界,也就是描述算法运行的最坏运行时间。回顾:插入排序算法中主要有2重循环,for循环和while循环,他们最多各执行n次,所以最坏运行时间或者说时间复杂度上界为O(n2)。没有必要计算算法每一行执行的时间以及每行执行的次数,然后求和,只需要考虑算法中主要循环执行的次数即可。擂韩化篓桂燕板愤德芒椭宅尼崇凤厅波惑语慨拯却酿失省姚沈雕坍勤充忧渐近符号算法渐近符号算法*Ω符号Ω符号:对于给定的函数g(n),记Ω(g(n))={f(n):存在c和n0,对于任意n≥n0,满足0≤cg(n)≤f(n)}的函数集。并记f(n)=Ω(g(n)),它表示f(n)是Ω(g(n))中的一个元素。定理:如果存在,且则必有f(n)=Ω(g(n))。直观含义:f(n)的阶不低于g(n)的阶。凋腮陆辖卓抽皱揉雹巢综讲秩舵归捕吵厕稿嚷冈郴下誉碰千茹廖纳祝丹泊渐近符号算法渐近符号算法