Getting Started with Data Structures Part 1 - Georgina Bishop

《Getting Started with Data Structures Part 1 - Georgina Bishop》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、GeorginaBishopGettingStartedwithDataStructuresPart1BookRixGmbH&Co.KG81669MunichCopyrightPageTableofContentsChapter1AlgorithmsandDataStructuresChapter2LinkedListChapter3ArrayListChapter4StackandQueueChapter5BinarySearchTreeChapter6SetChapter7SortingAlgorithmsDetail

2、edTableofContentsChapter1AlgorithmsandDataStructuresChapter1AlgorithmsandDataStructuresWhyDoWeCare?Iassumeyouareacomputerprogrammer.Perhapsyouareanewstudentofcomputerscienceormaybeyouareanexperiencedsoftwareengineer.Regardlessofwhereyouareonthatspectrum,algorithms

3、anddatastructuresmatter.Notjustastheoreticalconcepts,butasbuildingblocksusedtocreatesolutionstobusinessproblems.Sure,youmayknowhowtousetheC#ListorStackclass,butdoyouunderstandwhatisgoingonunderthecovers?Ifnot,areyoureallymakingthebestdecisionsaboutwhichalgorithmsa

4、nddatastructuresyouareusing?Meaningfulunderstandingofalgorithmsanddatastructuresstartswithhavingawaytoexpressandcomparetheirrelativecosts.AsymptoticAnalysisAsymptoticAnalysisWhenwetalkaboutmeasuringthecostorcomplexityofanalgorithm,whatwearereallytalkingaboutisperf

5、ormingananalysisofthealgorithmwhentheinputsetsareverylarge.Analyzingwhathappensasthenumberofinputsbecomesverylargeisreferredtoasasymptoticanalysis.Howdoesthecomplexityofthealgorithmchangewhenappliedtoten,oronethousand,ortenmillionitems?Ifanalgorithmrunsin5millisec

6、ondswithonethousanditems,whatcanwesayaboutwhatwillhappenwhenitrunswithonemillion?Willittake5secondsor5years?Wouldn’tyouratherfigurethisoutbeforeyourcustomer?Thisstuffmatters!RateofGrowthRateofgrowthdescribeshowanalgorithm’scomplexitychangesastheinputsizegrows.This

7、iscommonlyrepresentedusingBig-Onotation.Big-OnotationusesacapitalO(“order”)andaformulathatexpressesthecomplexityofthealgorithm.Theformulamayhaveavariable,n,whichrepresentsthesizeoftheinput.Thefollowingaresomecommonorderfunctionswewillseeinthisbookbutthislistisbyno

8、meanscomplete.Constant–O(1)AnO(1)algorithmisonewhosecomplexityisconstantregardlessofhowlargetheinputsizeis.The1doesnotmeanthatthereisonlyoneoperationort