计算机算法导论_第9章

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

1、IntroductiontoAlgorithms9MediansandOrderStatistics8/5/2021OrderStatisticsTheithorderstatisticinasetofnelementsistheithsmallestelementTheminimumisthusthe1storderstatisticThemaximumisthenthorderstatisticThemedianisthen/2orderstatisticIfniseven,thereare2medians8/5/2021SelectionProblemInput:

2、AsetAofn(distinct)numbersandanumberi,with1≤i≤n.Output:Theelementx∈Athatislargerthanexactlyi-1otherelementsofA.Howcanwecalculateorderstatistics?Whatistherunningtime?8/5/20219.1MinimumandMaximum8/5/2021MinimumandMaximumHowmanycomparisonsareneededtofindtheminimumelementinaset?Themaximum?MIN

3、IMUM(A)1min←A[1]2fori←2tolength[A]3doifmin>A[i]4thenmin←A[i]5returnmin8/5/2021SimultaneousMinimumandMaximumCanwefindtheminimumandmaximumwithlessthantwicethecost?Yes:WalkthroughelementsbypairsCompareeachelementinpairtotheotherComparethelargesttomaximum,smallesttominimumTotalcost:3comparis

4、onsper2elements≤3⌊n/2⌋=O(3n/2)8/5/20219.2Selectioninexpectedlineartime8/5/2021TheSelectionProblemAmoreinterestingproblemisselection:findingtheithsmallestelementofasetWewillshow:ApracticalrandomizedalgorithmwithO(n)expectedrunningtimeAcoolalgorithmoftheoreticalinterestonlywithO(n)worst-ca

5、serunningtime8/5/2021RandomizedSelectionKeyidea:usepartition()fromquicksortBut,onlyneedtoexamineonesubarrayThissavingsshowsupinrunningtime:O(n)Wewillagainuseaslightlydifferentpartitionq=RandomizedPartition(A,p,r)A[q]A[q]qpr8/5/2021RandomizedSelectionRandomizedSelect(A,p,r,i)if(p==r)the

6、nreturnA[p];q=RandomizedPartition(A,p,r)k=q-p+1;if(i==k)thenreturnA[q];if(i

7、ticseries)Nobetterthansorting!“Best”case:supposea9:1partitionT(n)=T(9n/10)+O(n)=???=O(n)(MasterTheorem,case3)Betterthansorting!Whatifthishadbeena99:1split?8/5/2021RandomizedSelection8/5/2021RandomizedSelection8/5/2021Calculatingexpectation8/5/2021Calculatingexpectation8/5