北京邮电大学 计算机学院 离散数学 3.2-Growth of Functions.ppt

《北京邮电大学 计算机学院 离散数学 3.2-Growth of Functions.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、GrowthofFunctions(函数增长)TheGrowthofFunctionsWequantifytheconceptthatggrowsatleastasfastasf.Whatreallymattersincomparingthecomplexityofalgorithms?Weonlycareaboutthebehaviorforlargeproblems.Evenbadalgorithmscanbeusedtosolvesmallproblems.Ignoreimplementationdetailssuchasloopcounterincrement

2、ation,etc.Wecanstraight-lineanyloop.2021/8/152CollegeofComputerScience&Technology,BUPTOrdersofGrowth(§3.2)Forfunctionsovernumbers,weoftenneedtoknowaroughmeasureofhowfastafunctiongrows.Iff(x)isfastergrowingthang(x),thenf(x)alwayseventuallybecomeslargerthang(x)inthelimit(forlargeenoughval

3、uesofx).Usefulinengineeringforshowingthatonedesignscalesbetterorworsethananother.2021/8/153CollegeofComputerScience&Technology,BUPTOrdersofGrowth-MotivationSupposeyouaredesigningawebsitetoprocessuserdata(e.g.,financialrecords).SupposedatabaseprogramAtakesfA(n)=30n+8microsecondstoprocess

4、anynrecords,whileprogramBtakesfB(n)=n2+1microsecondstoprocessthenrecords.Whichprogramdoyouchoose,knowingyou’llwanttosupportmillionsofusers?A2021/8/154CollegeofComputerScience&Technology,BUPTVisualizingOrdersofGrowthOnagraph,asyougototheright,thefaster-growingfunc-tionalwayseventual

5、lybecomesthelargerone...fA(n)=30n+8IncreasingnfB(n)=n2+1Valueoffunction2021/8/155CollegeofComputerScience&Technology,BUPTConceptoforderofgrowthWesayfA(n)=30n+8is(atmost)ordern,orO(n).Itis,atmost,roughlyproportionalton.fB(n)=n2+1isordern2,orO(n2).Itis(atmost)roughlyproportionalton2.A

6、nyfunctionwhoseexact(tightest)orderisO(n2)isfaster-growingthananyO(n)function.LaterwewillintroduceΘforexpressingexactorder.Forlargenumbersofuserrecords,theexactlyordern2functionwillalwaystakemoretime.2021/8/156CollegeofComputerScience&Technology,BUPTTheBig-ONotationDefinition:Letfandgbe

7、functionsfromNorRtoR.Thengasymptoticallydominates(渐进地支配)f,denotedfisO(g)or'fisbig-Oofg,iff$k$c"n[n>k®

8、f(n)

9、£c

10、g(n)

11、]“fisatmostorderg”,or“fisO(g)”,or“f=O(g)”alljustmeanthatfO(g).Note:ChoosekChoosec;itmaydependonyourchoiceofkOnceyouchoosekandc,youmustprovethetruthoftheimplicatio