计算机算法导论_第5章

《计算机算法导论_第5章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IntroductiontoAlgorithms计算机算法导论2007~2008年第一学期2下周五的实验课改在5月4日3QuizSolvethefollowingrecurrences(provideonlytheθ()bounds).YoucanassumeT(n)=1fornsmallerthansomeconstantinallcases.Youshouldwritethesolutionsandprovidejustifications.(20min)T(n)=T(n/7)+1T(n)=10T(n/3)+n1.1T(n)=T(n-2)+lgn4Answer1、T(n)=T(n/

2、7)+1Answer:T(n)=Θ(lgn)Master’sTheorem,case22、T(n)=10T(n/3)+n1.1Answer:T(n)=Θ(nlog310)Master’sTheorem,case15Answer3、T(n)=T(n-2)+lgnProbabilisticAnalysis&RandomizedAlgorithm75.1Thehiringproblem8Pseudocode9Computationofcost10Worst-caseanalysis11Probabilisticanalysis12ProbabilisticanalysisEssential

3、idea:HaveknowledgeormakeassumptionsaboutthedistributionofinputsTheexpectationisoverthisdistributionNeedareasonablecharacterizationoftheinputdistribution13Randomizedalgorithms14Randomizedalgorithms155.2Indicatorrandomvaribles16Example17Example18Analysisofthehiringproblem19Analysisofthehiringprobl

4、em20Analysisofthehiringproblem215.3Randomizedalgorithms22Randomizedalgorithms23RandomlypermutinganarrayPriority-basedmethodAssignarandompriorityintherange1ton3toeachpositionandthenreordersthearrayelementsintoincreasingpriorityorder.24Priority-basedmethodPermute-by-sorting(A)n←length[A]fori←1tond

5、oP[i]=RANDOM(1,n3)sortA,usingPassortkeysReturnATime:Θ(nlgn)25RandomlypermutinganarrayLemmaProcedurePERMUTE-BY-SORTINGproducesauniformrandompermutationoftheinput,assumingthatallprioritiesaredistinct.26RandomlypermutinganarrayPermutinginplaceruninlineartimewithoutrequiringsorting,andneedfewerrando

6、mbits27Permutinginplace28Permutinginplace29PermutinginplacePermutinginplace31Permutinginplace