Lecture note Data visualization - Chapter 17

The main contents of the chapter consist of the following: Remaining part of maximum contiguous subsequence sum problem, general big-oh rule, running time of algorithm.
Nội dung trích xuất từ tài liệu:
Lecture note Data visualization - Chapter 17Lecture17RecapRemainingPartofMaximumContiguousSubsequence SumProblemGeneralBigOhRule BigOh BigOmega BigTheta LittleOhRunningTimeofAlgorithmRunningTimeofCubicAlgorithmRunningTimeofQuadraticAlgorithmRunningTimeofLinearAlgorithm Asimilarcalculationshowsthata10foldincreasein inputsizeresultsina10foldincreaseinrunningtimeThisrelationshiphasbeenconfirmedexperimentallyForalinearprogramthetermsufficientlylargemeansa somewhathigherinputsizethanfortheotherprogramsThereasonisthatoftheoverheadof0.000003secis usedinallcasesForalinearprogram,thistermisstillsignificantfor moderateinputsizesRunningTimeofLogarithmicTermsTheLogarithmThelistoftypicalgrowthratefunctionsincludesseveral entriescontainingthelogarithmAlogarithmistheexponentthatindicatesthepowerto whichanumber(thebase)israisedtoproduceagiven numberDefinitionofLogarithmTheorem6.4LogarithmContinued….BitsinaBinaryNumberRepeatedDoublingRepeatedHalvingContinued….Manyofthealgorithmscontainlogarithms,becauseofthe repeatedhalvingprinciple,whichholdsthat,startingatN, wecanhalveonlylogarithmicallymanytimesInotherwords,analgorithmisO(logN)ifittakes constant(O(1))timetocuttheproblemsizebyaconstant fraction(usually112)Thisconditionfollowsdirectlyfromthefactthatthere willbeO(logN)iterationsoftheloopAnyconstantfractionwilldobecausethefractionis reflectedinthebaseofthelogarithm,andTheorem6.4 tellsusthatthebasedoesnotmatterTheorem6.5StaticSearchingProblemAnimportantuseofcomputersistolookupdataIfthedataarenotallowedtochange(e.g.,itisstoredona CDROM),wesaythatthedataarestaticAstaticsearchaccessesdatathatareneveralteredProblem GIVENANINTEGERXANDANARRAYA, RETURNTHEPOSITIONOFXINAORAN INDICATIONTHATITISNOTPRESENT.IFX OCCURSMORETHANONCE,RETURNANY OCCURRENCE.THEARRAYAISNEVER ALTERED.SolutionAnexampleofstaticsearchingislookingupapersonin thetelephonebookTheefficiencyofastaticsearchingalgorithmdependson whetherthearraybeingsearchedissortedInthecaseofthetelephonebook,searchingbynameis fast,butsearchingbyphonenumberishopelessSomesolution SequentialSearch BinarySearch SequentialSearchWhentheinputarrayhasnotbeensorted,wehavelittle choicebuttodoalinearsequentialsearchthatsteps throughthearraysequentiallyuntilamatchisfoundThecomplexityofthealgorithmisanalyzedinthreeways First,weprovidethecostofanunsuccessfulsearch Second,wegivetheworstcasecostofasuccessfulsearch Finally,wefindtheaveragecostofasuccessfulsearchAnalyzingsuccessfulandunsuccessfulsearches separatelyistypicalContinued….Anunsuccessfulsearchrequirestheexaminationofevery iteminthearray,sothetimewillbeO(N)Intheworstcase,asuccessfulsearch,too,requiresthe examinationofeveryiteminthearraybecausewemight notfindamatchuntilthelastitem.Thustheworstcase runningtimeforasuccessfulsearchisalsolinearOnaverage,however,wesearchonlyhalfanarray.That is,foreverysuccessfulsearchinpositioni,thereisa correspondingsuccessfulsearchinpositionN1iHowever,N/2isstillO(N)