（减治法减可变规模算法）ppt课件.ppt

《（减治法减可变规模算法）ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DecreaseandConquer(III)Chapter5Variable-Size-DecreaseAlgorithmsSelectionProblemThekthsmallestelementfindproblemSearchProblemInterpolationSearchCombinatoryProblemThegameofNimGoalsoftheLectureAttheendofthislecture,youshouldUnderstandwhat’sselectionproblem

2、andmasterthepartitionbasedalgorithmforfindingthekthsmallestelementsMasterthebasicideaofinterpolationsearchandknowthedifferencesbetweenbinarysearchandinterpolationsearchKnowhowtosolvethegameofnimSelectionProblemWhat’sselectionproblem?Istofindaparticulare

3、lementofanunsortedlistClassicalselectionproblemGenerally,findthekthsmallestelementFindthemaximumorminimumelementsorthebothFindthemedianelementThemedianisusedinstatisticsasameasureofanaveragevalueofasample.Infact,itisabetter(morerobust)indicatorthantheme

4、an,whichisusedforthesamepurpose.Example:4,1,10,9,7,12,8,2,15median=?Findthekthelement(directidea)Tofindthekthsmallestelement,wecouldmovetheksmallestelementstothestartofthelistandthenthekthsmallestwillbeinlocationlist[k]Thisinvolvesfindingthesmallestelem

5、entandmovingittothefirstplace,thenfindingthesecondsmallestelementandmovingittothesecondplaceandsoonDirectIdeaAlgorithmFindkthSmallestBF(A[0…n-1],k)//Input:AnarrayAoforderableelementsandintegerk(1≤k≤n)//Output:ThevalueofthekthsmallestelementinA[0…n-1]for

6、i0tok-1smallestLocationn-1forjn-2toiifA[j]

7、comparisonsOnthesecondpass,wecomparethelastelementtotherest(exceptthefirstelement),doingn-2comparisons,andsoonAlgorithmsbasedonVariable-Size-DecreaseTechniqueAfasteralgorithmisbasedonusingthequicksort-likepartitionofthelist.Letsbeasplitpositionobtained

8、byapartition:Assumingthatthelistisindexedfrom1ton:Ifs=k,theproblemissolved;ifs>k,lookforthek-thsmallestelem.intheleftpart;ifs