Lecture note Data visualization - Chapter 18

This chapter presents the following content: Running time of function, running time of cubic function, running time of quadratic function, running time of linear function, running time of logarithmic function, logarithm, static searching problem,...
Nội dung trích xuất từ tài liệu:
Lecture note Data visualization - Chapter 18Lecture18RecapRunningTimeofFunction RunningTimeofCubicFunction RunningTimeofQuadraticFunction RunningTimeofLinearFunction RunningTimeofLogarithmicFunctionLogarithm BitsinBinaryNumbers RepeatedDoubling RepeatedHalvingCheckinganAlgorithmAnalysisOncewehaveperformedanalgorithmanalysis,wewant todeterminewhetheritiscorrectandasgoodwecan possiblymakeitOnewaytodosoistocodetheprogramandseeifthe empiricallyobservedrunningtimematchestherunning timepredictedbytheanalysisContinued….WhenNincreasesbyafactorof10,therunningtimegoes upbyafactorof10forlinearprograms,100forquadratic programs,and1000forcubicprogramsProgramsthatruninO(NlogN)takeslightlymorethan 10timesaslongtorununderthesamecircumstancesTheseincreasescanbehardtospotifthelowerorder termshaverelativelylargecoefficientsandNisnotlarge enoughAnexampleisthejumpfromN=10toN=100inthe runningtimeforthevariousimplementationsofthe maximumcontiguoussubsequencesumproblemContinued….Anothercommonlyusedtricktoverifythatsomeprogram isO(F(N))istocomputethevaluesT(N)/F(N)forarange ofN,whereT(N)istheempiricallyobservedrunningtimeIfF(N)isatightanswerfortherunningtime,the computedvaluesconvergetoapositiveconstantIfF(N)isanoverestimate,thevaluesconvergetozeroIfF(N)isanunderestimate,andhencewrong,thevalues divergeExampleEmpiricalrunningtimeforNbinarysearchesinanNitemarrayContinued….Noteinparticularthatwedonothavedefinitive convergenceOneproblemisthattheclockthatweusedtotimethe programticksonlyevery10msNotealsothatthereisnogreatdifferencebetweenO(N) andO(NlogN)CertainlyanO(NlogN)algorithmismuchcloserto beinglinearthanbeingquadraticFinally,notethatthemachineinthisexamplehasenough memorytostore640,000objectsLimitationsofBigOhAnalysisBigOhanalysisisaveryeffectivetool,butitdoeshave limitationsItsuseisnotappropriateforsmallamountsofinputForsmallamountsofinput,usethesimplestalgorithmAlso,foraparticularalgorithm,theconstantimpliedby theBigOhmaybetoolargetobepractical Forexample:ifonealgorithmsrunningtimeisgoverned bytheformula2NlogNandanotherhasarunningtimeof 1000N,thefirstalgorithmwouldmostlikelybebetter,even thoughitsgrowthrateislargerContinued….Largeconstantscancomeintoplaywhenanalgorithmis excessivelycomplexTheyalsocomeintoplaybecauseouranalysisdisregards constantsandthuscannotdifferentiatebetweenthingslike memoryaccessanddiskaccessOuranalysisassumesinfinitememory,butinapplications involvinglargedatasets,lackofsufficientmemorycanbe asevereproblemContinued….Sometimes,evenwhenconstantsandlowerorderterms areconsidered,theanalysisisshownempiricallytobean overestimateInthiscase,theanalysisneedstobetightened.Orthe averagecaserunningtimeboundmaybesignificantlyless thantheworstcaserunningtimebound,andsono improvementintheboundispossibleFormanycomplicatedalgorithmstheworstcaseboundis achievablebysomebadinput,butinpracticeitisusually anoverestimateTwoexamples:Continued….However,worstcaseboundsareusuallyeasiertoobtain thantheiraveragecasecounterpartsForexample:amathematicalanalysisoftheaveragecase runningtimeofShellsorthasnotbeenobtainedSometimes,merelydefiningwhataveragemeansis difficultWeuseaworstcaseanalysisbecauseitisexpedientand alsobecause,inmostinstances,theworstcaseanalysisis verymeaningfulInthecourseofperformingtheanalysis,wefrequentlySummaryofChapterInthischapterweintroducedalgorithmanalysisand showedthatalgorithmicdecisionsgenerallyinfluencethe runningtimeofaprogrammuchmorethanprogramming tricksdoWealsoshowedthehugedifferencebetweentherunning timesforquadraticandlinearprogramsandillustratedthat cubicalgorithmsare,forthemostpart,unsatisfactoryWeexaminedanalgorithmthatcouldbeviewedasthe basisforourfirstdatastructureThebinarysearchefficientlysupportsstaticoperations therebyprovidingalogarithmicworstcasesearchCommonErrorsContinued…. DataStructuresandAlgorithmswithMatlabMATLABEnvironmentMATLABopeningwindowMATLABWindowsCommandwindowCommandHistoryWorkspaceWindowCurrentFolderWindowDocumentWindowGraphicsWindowEditWindowStartButtonCommandWindowThecommandwindowislocatedinthecenterpaneofthe defaultviewoftheMATLABscreenThecommandwindowoffersanenvironmentsimilartoa scratchpadUsingitallowsyoutosavethevaluesyoucalculate,but notthecommandsusedtogeneratethosevaluesIfyouwanttosavethecommandsequence,youwillneed tousetheeditingwindowtocreateanMfile.Both approachesarevaluable. ...