资源描述:
《北京邮电大学 计算机学院 离散数学 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+8IncreasingnfB(n)=n2+1Valueoffunction2021/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)”alljustmeanthatfO(g).Note:ChoosekChoosec;itmaydependonyourchoiceofkOnceyouchoosekandc,youmustprovethetruthoftheimplicatio