Lecture note Data visualization - Chapter 16

This chapter presents the following content: Introduction to algorithm analysis, different functions, function’s growth rate, three problems related to algorithm running time, maximum contiguous subsequence sum problem.
Nội dung trích xuất từ tài liệu:
Lecture note Data visualization - Chapter 16Lecture16RecapIntroductiontoAlgorithmAnalysisDifferentFunctionsFunction’sGrowthRateThreeProblemsRelatedtoAlgorithmRunningTime FindMinimuminanArray FindClosestPointinaPlane FindCollinearPointsinaPlaneMaximumContiguousSubsequenceSumProblemTheorem6.1ProofPlacethefollowingN+2ballsinabox:Nballs numbered1throughN,oneunnumberedredballandone unnumberedblueball.Removethreeballsfromthebox.Ifaredballisdrawn,numberitasthelowestofthe numberedballsdrawn.Ifablueballisdrawn,numberitashighestofthe numberedballsdrawn.Notethatifyoudrawbotharedandablueball,thenthe effectistohavethreeballsidenticalnumbered.Orderthe threeballs.Eachsuchordercorrespondstoatripletsolutiontothe1//Quadraticmaximumcontiguoussubsequencesum algorithm.2//seqStartandseqEndrepresenttheactualbest sequence.3template4ComparablemaxSubsequenceSum(const vector&a,5 int&seqstart,int&seqEnd)6(7intn=a.size();8ComparablemaxSum=0;9LinearAlgorithmTomovefromaquadraticalgorithmtoalinearalgorithm, weneedtoremoveyetanotherloopTheproblemisthatthequadraticalgorithmisstillan exhaustivesearch;thatis,wearetryingallpossible subsequencesTheonlydifferencebetweenthequadraticandcubic algorithmsisthatthecostoftestingeachsuccessive subsequenceisaconstantO(1)insteadoflinearO(N)Becauseaquadraticnumberofsubsequencesarepossible, theonlywaywecanattainasubquadraticboundistofind acleverwaytoeliminatefromconsiderationalargeTheorem6.2LinearAlgorithmContinued….Theorem6.31//Linearmaximumcontiguoussubsequencesum algorithm.2//seqStartandseqEndrepresenttheactualbest sequence.3template4ComparablemaxSubsequenceSum(const vector&a,5int&seqstart,int&seqEnd)6{7intn=a.size();8Comparablethissum=0;9ComparablemaxSum=0;LinearAlgorithmContinued….AccordingtoTheorem6.3whenanegativesubsequence isdetected,notonlycanwebreaktheinnerloop,butwe canalsoadvanceitoj+1Therunningtimeofthisalgorithmislinear:Ateachstep intheloop,weadvancej,sotheloopiteratesatmostN timesThecorrectnessofthisalgorithmismuchlessobvious thanforthepreviousalgorithms,whichistypical.Thatis, algorithmsthatusethestructureofaproblemtobeatan exhaustivesearchgenerallyrequiresomesortof correctnessproofWeprovedthatthealgorithmiscorrectbyusingashortGeneralBigOhRulesBigOhNotationBigOmegaNotationBigThetaNotationLittleOhNotationSummaryofFourDefinitionRunningTimeofAlgorithmsTherunningtimeofstatementsinsideagroupofnested loopsistherunningtimeofthestatementsmultipliedby thesizesofalltheloopsTherunningtimeofasequenceofconsecutiveloopsis therunningtimeofthedominantloopThetimedifferencebetweenanestedloopinwhichboth indicesrunfrom1toNandtwoconsecutiveloopsthatare notnestedbutrunoverthesameindicesisthesameasthe spacedifferencebetweenatwodimensionalarrayandtwo onedimensionalarrays Thefirstcaseisquadratic