資源描述：
《lecture 2 asymptotic notation》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、MITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlgorithms,Fall2005Pleaseusethefollowingcitationformat:ErikDemaineandCharlesLeiserson,6.046JIntroductiontoAlgorithms,Fall2005.(MassachusettsInstituteofTechnology:MITOpenCourseWare).http://ocw.mit.edu(accessedMMDD,YYYY)
2、.License:CreativeCommonsAttribution-Noncommercial-ShareAlike.Note:Pleaseusetheactualdateyouaccessedthismaterialinyourcitation.FormoreinformationaboutcitingthesematerialsorourTermsofUse,visit:http://ocw.mit.edu/termsMITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlg
3、orithms,Fall2005Transcript–Lecture2MynameisErikDemaine.YoushouldcallmeErik.Welcomebackto6.046.ThisisLecture2.AndtodaywearegoingtoessentiallyfillinsomeofthemoremathematicalunderpinningsofLecture1.So,Lecture1,wejustsortofbarelygotourfeetwetwithsomeanalysisofalgorithms,insert
4、ionsortandmergesort.Andweneededacoupleoftools.Wehadthisbigideaofasymptoticsandforgettingaboutconstants,justlookingattheleadterm.Andso,today,we'regoingtodevelopasymptoticnotationsothatweknowthatmathematically.Andwealsoendedupwitharecurrencewithmergesort,therunningtimeofmerg
5、esort,soweneedtoseehowtosolverecurrences.Andwewilldothosetwothingstoday.Question?Yes,Iwillspeaklouder.Thanks.Good.EventhoughIhaveamicrophone,Iamnotamplified.OK,solet'sstartwithasymptoticnotation.Wehaveseensomebasicasymptoticnotation.Iamsureyouhaveseenitinotherclassesbefore
6、,thingslikebigO-notation.Andtodaywearegoingtoreallydefinethisrigorouslysoweknowwhatistrueandwhatisnot,whatisvalidandwhatisnot.Wearegoingtodefine,andunfortunatelytodayisgoingtobereallymathematicalandreallynoalgorithmstoday,whichissortofananticlimax.Butnextlecturewewilltalka
7、boutrealalgorithmsandwillapplyallthethingswelearnedtodaytorealalgorithms.ThisisbigO-notation,capitalO-notation.Wehavef(n)=O[g(n)].Thismeansthattherearesomesuitableconstants,candn_o,suchthatfisboundedbycg(n)forallsufficientlylargen.So,thisisprettyintuitivenotion.Wehaveseeni
8、tbefore.Wearegoingtoassumethatf(n)isnon-negativehere.AndIjustwantf(n)tobeboundedabovebyg(
