资源描述：
《算法分析经典教材 麻省理工学院版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ReadingMaterialChapter1:TheRoleofAlgorithmsinComputingWhatarealgorithms?Whyisthestudyofalgorithmsworthwhile?Whatistheroleofalgorithmsrelativetoothertechnologiesusedincomputers?Inthischapter,wewillanswerthesequestions.1.1AlgorithmsInformally,analgorithmisanywell-definedcomputationalproceduretha
2、ttakessomevalue,orsetofvalues,asinputandproducessomevalue,orsetofvalues,asoutput.Analgorithmisthusasequenceofcomputationalstepsthattransformtheinputintotheoutput.Wecanalsoviewanalgorithmasatoolforsolvingawell-specifiedcomputationalproblem.Thestatementoftheproblemspecifiesingeneraltermsthedesir
3、edinput/outputrelationship.Thealgorithmdescribesaspecificcomputationalprocedureforachievingthatinput/outputrelationship.Forexample,onemightneedtosortasequenceofnumbersintonondecreasingorder.Thisproblemarisesfrequentlyinpracticeandprovidesfertilegroundforintroducingmanystandarddesigntechniquesa
4、ndanalysistools.Hereishowweformallydefinethesortingproblem:·Input:Asequenceofnnumbers〈a1,a2,...,an〉.·Output:Apermutation(reordering)〈a1’,a2’,...,an’〉oftheinputsequencesuchthata1’≤a2’≤...≤an’.Forexample,giventheinputsequence〈31,41,59,26,41,58〉,asortingalgorithmreturnsasoutputthesequence〈26,31,4
5、1,41,58,59〉.Suchaninputsequenceiscalledaninstanceofthesortingproblem.Ingeneral,aninstanceofaproblemconsistsoftheinput(satisfyingwhateverconstraintsareimposedintheproblemstatement)neededtocomputeasolutiontotheproblem.Sortingisafundamentaloperationincomputerscience(manyprogramsuseitasanintermedi
6、atestep),andasaresultalargenumberofgoodsortingalgorithmshavebeendeveloped.Whichalgorithmisbestforagivenapplicationdependson-amongotherfactors-thenumberofitemstobesorted,theextenttowhichtheitemsarealreadysomewhatsorted,possiblerestrictionsontheitemvalues,andthekindofstoragedevicetobeused:mainme
7、mory,disks,ortapes.Analgorithmissaidtobecorrectif,foreveryinputinstance,ithaltswiththecorrectoutput.Wesaythatacorrectalgorithmsolvesthegivencomputationalproblem.Anincorrectalgorithmmightnothaltatallonsomeinputinstances,oritmighthaltwith
