GrowthofFunctions(函數增加)2/10/10CollegeofComputerScience&Technology,BUPTTheGrowthofFunctionsWequantifytheconceptthatg

growsatleastasfastasf.Whatreallymattersincomparingthecomplexityofalgorithms?Weonlycareaboutthebehaviorforlarge

problems.Evenbadalgorithmscanbeusedtosolvesmallproblems.Ignoreimplementationdetailssuchasloopcounterincrementation,etc.Wecanstraight-lineanyloop.3/10/10CollegeofComputerScience&Technology,BUPTOrdersofGrowth(§3.2)Forfunctionsovernumbers,weoftenneedtoknowaroughmeasureofhowfastafunctiongrows.Iff(x)isfastergrowingthang(x),thenf(x)alwayseventuallybecomeslargerthang(x)inthelimit(forlargeenoughvaluesofx).Usefulinengineeringforshowingthatonedesignscalesbetterorworsethananother.4/10/10CollegeofComputerScience&Technology,BUPTOrdersofGrowth-MotivationSupposeyouaredesigningawebsitetoprocessuserdata(e.g.,financialrecords).SupposedatabaseprogramAtakesfA(n)=30n+8microsecondstoprocessanynrecords,whileprogramBtakesfB(n)=n2+1microsecondstoprocessthenrecords.Whichprogramdoyouchoose,knowingyou’llwanttosupportmillionsofusers?A5/10/10CollegeofComputerScience&Technology,BUPTVisualizingOrdersofGrowthOnagraph,as

yougotothe

right,thefaster-

growingfunc-

tionalways

eventually

becomesthe

largerone...fA(n)=30n+8IncreasingnfB(n)=n2+1Valueoffunction6/10/10CollegeofComputerScience&Technology,BUPTConceptoforderofgrowthWesayfA(n)=30n+8

is(atmost)

ordern,orO(n).Itis,atmost,roughlyproportionalton.fB(n)=n2+1isordern2,orO(n2).Itis(atmost)roughlyproportionalton2.Anyfunctionwhoseexact(tightest)

orderisO(n2)isfaster-growingthananyO(n)function.LaterwewillintroduceΘforexpressingexactorder.Forlargenumbersofuserrecords,theexactlyordern2functionwillalwaystakemoretime.7/10/10CollegeofComputerScience&Technology,BUPTTheBig-ONotationDefinition:LetfandgbefunctionsfromNorRtoR.Theng

asymptoticallydominates(漸進地支配)f,denotedfisO(g)or'fisbig-Oofg,iff$k$c"n[n>k?|f(n)|￡c|g(n)|]“fisatmostorderg”,or“fisO(g)”,or“f=O(g)”alljustmeanthatfO(g).Note:ChoosekChoosec;itmaydependonyourchoiceofkOnceyouchoosekandc,youmustprovethetruthoftheimplication(oftenbyinduction)8/10/10CollegeofComputerScience&Technology,BUPTPointsaboutthedefinitionNotethatfisO(g)solongasanyvaluesofcandkexistthatsatisfythedefinition.But:Theparticularc,k,valuesthatmakethestatementtruearenotunique:Anylargervalueofcand/orkwillalsowork.

Youarenotrequiredtofindthesmallestcandkvaluesthatwork.(Indeed,insomecases,theremaybenosmallestvalues!)However,youshouldprovethatthevaluesyouchoosedowork.9/10/10CollegeofComputerScience&Technology,BUPTlittle-oofgIncalculusIfThenfiso(g)(calledlittle-oofg)10/10/10CollegeofComputerScience&Technology,BUPTTheoremIffiso(g)thenfisO(g).Proof:bydefinitionoflimitasngoestoinfinity,f(n)/g(n)getsarbitrarilysmall.Thatisforanye>0,theremustbeanintegerNsuchthatwhenn>N,|f(n)/g(n)|<e.Hence,choosec=e

andk=N.Q.E.D.11/10/10CollegeofComputerScience&Technology,BUPTExample3n+5isO(n2)Proof:It'seasytoshowusingthetheoryoflimits.Hence3n+5iso(n2)andsoitisO(n2).Q.E.D.12/10/10CollegeofComputerScience&Technology,BUPTExample13/10/10CollegeofComputerScience&Technology,BUPT“Big-O”ProofExamplesShowthat30n+8isO(n).Showc,k:n>k:

30n+8cn.Letc=31,k=8.Assumen>k=8.Then

cn=31n=30n+n>30n+8,so30n+8<cn.Showthatn2+1isO(n2).Showc,k:n>k:n2+1cn2.Letc=2,k=1.Assumen>1.Then

cn2=2n2=n2+n2>n2+1,orn2+1<cn2.14/10/10CollegeofComputerScience&Technology,BUPTNote30n+8isn’t

lessthann

anywhere(n>0).Itisn’teven

lessthan31n

everywhere.Butitislessthan

31n

everywhereto

therightofn=8.n>k=8Big-Oexample,graphicallyIncreasingnValueoffunctionn30n+8cn=

31n30n+8

O(n)15/10/10CollegeofComputerScience&Technology,BUPTSomeimportantBig-OresultsTheorem1Letf(x)=anxn

+

an-1xn-1

+…+a1x+a0

,wherea0,

a1,

…an-1,an

arerealnumbers.Thenf(x)isO(xn).n!isO(nn)logn!isO(nlogn)lognisO(n)1,logn,n,nlogn,n2,2n,n!16/10/10CollegeofComputerScience&Technology,BUPTThegrowthofcombinationsoffunctionsTheorem2Supposethatf1isO(g1)andf2isO(g2).Thenf1+f2isO(max{g1,g2})Corollary1Iff1,f2arebothO(g)thenf1+f2isO(g).Theorem3Supposethatf1isO(g1)andf2isO(g2).Thenf1f2isO(g1g2)17/10/10CollegeofComputerScience&Technology,BUPTProofoff1f2isO(g1g2)Thereisak1andc1suchthat1.f1(n)<c1g1(n)whenn>k1.Thereisak2andc2suchthat2.f2(n)<c2g2(n)whenn>k2.Wemustfindak3andc3suchthat3.f1(n)f2(n)<c3g1(n)g2(n)whenn>k3.18/10/10CollegeofComputerScience&Technology,BUPTProofoff1f2isO(g1g2)Weusetheinequalityif0<a<band0<c<dthenac<bdtoconcludethatf1(n)f2(n)<c1c2g1(n)g2(n)aslongask>max{k1,k2}sothatbothinequalities1and2.holdatthesametime.Therefore,choosec3=c1c2andk3=max{k1,k2}.Q.E.D.19/10/10CollegeofComputerScience&Technology,BUPTExampleFindthecomplexityclassofthefunction(nn!+3n+2

+3n100)(nn

+n2n

)Solution:Thismeanstosimplifytheexpression.Throwoutstuffwhichyouknowdoesn'tgrowasfast.Andatlast:nn!nn20/10/10CollegeofComputerScience&Technology,BUPTBig-omeganotationDefinition:LetfandgbefunctionsfromNorRtoR.Wesayfis(g)or'fisbig-ofg,'iff$k$c"n[n>k?|f(n)|c|g(n)|]Note:ChoosekChoosec;itmaydependonyourchoiceofkOnceyouchoosekandc,youmustprovethetruthoftheimplication(oftenbyinduction)21/10/10CollegeofComputerScience&Technology,BUPTBig-thetanotationIffO(g)andgO(f),thenwesay“gandfareofthesameorder”or“fis(exactly)orderg”andwritef(g).Another,equivalentdefinition:

(g){f:RR|

c1c2k>0x>k:|c1g(x)||f(x)||c2g(x)|}“Everywherebeyondsomepo