资源描述：
《five algorithms you must know》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、5algorithmsyoumustknow(2007-11-1418:58)分类：C语言相关Sorting-Themostfundamentalthinginalgorithms,andit'salmostagiven.(AnditmeansthesameinEnglishasitdoesinMath,sonoexplanationsneeded,Ihope.)Therearetonsofcrazysortsoutthere,butquicksortistheoneeveryoneshouldbefamiliarwith,merges
2、ortistheonethatcomesinhandywhenyoucan'tfiteverythingintoRAM,andintrospectivesortisimportanttolearn,becauseitteachesusanimportantparadigm-youdon'tneedtofindanalgorithmthatdoeseverythingthebest-usethebestalgorithmforeachtestcase!RealWorldApplication:You'reinalibrary,givena
3、bunchofbooks.Youwantbeabletolookforbookswithoutlookingateverybookeverytime.Sortthemanddoquickchecks!BinarySearch-ThisistheclassicexampleofDivideandConquer.Rememberthatgame20questions?Youhavetoask20questionstoguessaword.Well,thewaytocheatistonarrowitdownhalfwayeverytime.T
4、heEnglishDictionaryhasabout500,000words,meaningyouwouldstillhavequeriestospare.Yes,itwouldbeboring,butitwouldgosomethinglikethis:Doesyourwordcomebeforetheword"marry"?YesDoesyourwordcomebeforetheword"gerrymander"?Yougetthepoint.Assumingyoualreadyknowyouhavetosort,youcanbi
5、narysearchatO(log_2N).Whichforsay,atrillion,islessthan50.Butitsapplicationdoesn'tstopthere,asit(aswellasitscousinternarysearch)canhelpyousolvenumericalequations(thisisactuallycallbisection,butsameparadigm).Forexample,youwanttofindthecuberootofN(N^(1/3)),butdon'thavesomes
6、ortoflibraryready.Easysolution?Binarysearch!Youknowx=y^3,so"guess"avalueforx,andgofromthere!RealWorldApplication:Accordingtofolklore,ProfessorSkienawoulddemonstratebinarysearchbyaskingforaname,andthenlookingitupinthephonebookbycheckingthemiddleofthebook,doesacomparison,a
7、ndliterallytearouthalfthebookandthrowitinthetrash.Youcanprobablycomeupwithalessdramaticexample.Hashing-Conceptuallyeasy,ifonlybecausemostclasseshopoverthiswithidealizations.ThelegendaryUdiManberwasfondofsaying,"hashing,hashing,hashing".No,realhashingishard,butdon'tbeafra
8、idtouseit.Imagineyouhaveaclosetfullofshirts.It'sveryhardtofindashirt.Sowhatcanyoudo?Hashit.Takeeveryshi
