12-13-01ADA11(减治法-减可变规模算法)

DecreaseandConquer(III)Chapter5Variable-Size-DecreaseAlgorithmsSelectionProblemThekthsmallestelementfindproblemSearchProblemInterpolationSearchCombinatoryProblemThegameofNim2020/10/3132012-2013-01《DesignandAnalysisofAlgorithm》SCUNGoalsoftheLectureAttheendofthislecture,youshould•Understandwhat’sselectionproblemandmasterthepartitionbasedalgorithmforfindingthekthsmallestelements•Masterthebasicideaofinterpolationsearchandknowthedifferencesbetweenbinarysearchandinterpolationsearch•Knowhowtosolvethegameofnim2020/10/3142012-2013-01《DesignandAnalysisofAlgorithm》SCUNSelectionProblemWhat’sselectionproblem?•IstofindaparticularelementofanunsortedlistClassicalselectionproblem•Generally,findthekthsmallestelement•Findthemaximumorminimumelementsortheboth•Findthemedianelement–Themedianisusedinstatisticsasameasureofanaveragevalueofasample.Infact,itisabetter(morerobust)indicatorthanthemean,whichisusedforthesamepurpose.–Example:4,1,10,9,7,12,8,2,15median=?2020/10/3152012-2013-01《DesignandAnalysisofAlgorithm》SCUNFindthekthelement(directidea)Tofindthekthsmallestelement,wecouldmovetheksmallestelementstothestartofthelistandthenthekthsmallestwillbeinlocationlist[k]Thisinvolvesfindingthesmallestelementandmovingittothefirstplace,thenfindingthesecondsmallestelementandmovingittothesecondplaceandsoon2020/10/3162012-2013-01《DesignandAnalysisofAlgorithm》SCUNDirectIdeaAlgorithmFindkthSmallestBF(A[0…n-1],k)//Input:AnarrayAoforderableelementsandintegerk(1≤k≤n)//Output:ThevalueofthekthsmallestelementinA[0…n-1]fori0tok-1smallestLocationn-1forjn-2toiifA[j]A[smallestLocation]smallestLocation=jendifendforswap(A[i],A[smallestLocation])endforReturnA[k-1]2020/10/3172012-2013-01《DesignandAnalysisofAlgorithm》SCUNDirectIdeaAlgorithmAnalysisWeneedtodokpasses,thusgiving1(1)T()()()2kikknninkOnkOnthefirstpass,wecomparethelastelementtotherest,doingn-1comparisonsOnthesecondpass,wecomparethelastelementtotherest(exceptthefirstelement),doingn-2comparisons,andsoon82012-2013-01《DesignandAnalysisofAlgorithm》SCUNAlgorithmsbasedonVariable-Size-DecreaseTechniqueAfasteralgorithmisbasedonusingthequicksort-likepartitionofthelist.Letsbeasplitpositionobtainedbyapartition:Assumingthatthelistisindexedfrom1ton:Ifs=k,theproblemissolved;ifsk,lookforthek-thsmallestelem.intheleftpart;ifsk,lookforthe(k-s)thsmallestelem.intherightpart.sallare≤A[s]allare≥A[s]Note:Thesameideacanbeimplementedwithoutrecursionaswell.Forthenonrecursiveversion,weneednotevenadjustthevalueofkbutjustcontinueuntils=k.2020/10/3192012-2013-01《DesignandAnalysisofAlgorithm》SCUNTracingtheMedian/SelectionAlgorithmExample:411097128215Here:n=9,k=9/2=5arrayindex123456789411097128215412971281015214971281015---s=3k=5971281015978121015879121015---s=6k=58778---s=k=5Solution:medianis82020/10/31102012-2013-01《DesignandAnalysisofAlgorithm》SCUNAlgorithmsbasedonvariable-size-decreasetechniqueFindkthSmallestVSD_NR(A[0…n-1],k)//Input:AnarrayAoforderableelementsandintegerk(1≤k≤n)//Output:ThevalueofthekthsmallestelementinA[0…n-1]l←0;r←n-1Whilel≤rp←A[l];j←lfori←l+1torifA[i]≤pj←j+1ifj≠iswap(A[j],A[i])swap(A[l],A[j])ifjk-1r←j-1elseifjk-1l←j+1elsereturnA[k-1]PartitionalgorithmThinking:Howtorewritethisalgorithminrecursiveformat?j←partition2(A,l,r)//j←partition2(A,l,r)2020/10/31112012-2013-01《DesignandAnalysisofAlgorithm》SCUNBestCaseAnalysisTheaboverecurrenceworksouttoTB(n)=2n–1+logn=(n)T()T()12T(1)1BBBnnnSowecangetthenumberofcomparisonrecurrencerelationAccordingtothePartitionalgorithm,ifthelistisdividedinhalfeachtime,thiswillleadtothebestcase.ThePartitionAlgorithmwilldon-1comparisonsforalistofsizen2020/10/31122012-2013-01《DesignandAnalysisofAlgorithm》SCUNWorstCaseAnalysisTheaboverecurrenceworksouttoTW(n)=(n+2)*k-k*(k+1)/2=O(n*k)T()T(1)1WWnnnAccordingtothePartitionalgorithm,ifthelistisdividedbyn-1to0,thiswillleadtotheworstcase.ThePartitionAlgorithmwilldon-1comparisonsforalistofsizenSowecangetthenumberofcomparisonrecurrencerelation2020/10/31132012-2013-01《DesignandAnalysisofAlgorithm》SCUNAverage-CaseAnalysisThiswouldworkouttoTA(n)≤4n,soTA(n)=(n)2101T()1[T(1)T()]knAAAjjknnnjjnSowecangetIneachpatition,therecouldbenplacesforthepivotforalistofsizen,Wewillconsidereachofthesetobeequivalentandsowillgiveeachaprobabilityof1/nThePartitionAlgorithmwilldon-1comparisonsforalistofsizen2020/10/31142012-2013-01《DesignandAnalysisofAlgorithm》SCUNAnalysisSummaryNumberofcomparisons:•Thebestcase:(n)•Theworstcase:O(kn)•Theaveragecase:(n)ImprovethealgorithmsuchthatitrunsinworstcasewithO(n)comparisons!•Seereferencebook:algorithmsdesigntechniquesandanalysis,Alsuwaiyel.2020/10/31152012-2013-01《DesignandAnalysisofAlgorithm》SCUNInterpolationSearchSearchesasortedarraysimilartobinarysearchbutestimateslocationofthesearchkeyinA[l..r]byusingitsvaluev.Specifically,thevaluesofthearray’selementsareassumedtogrowlinearlyfromA[l]toA[r]andthelocationofvisestimatedasthex-coordinateofthepointonthestraightlinethrough(l,A[l])and(r,A[r])whosey-coordinateisv:indexvalueA[r]vA[l]lxr..)[][]vlrlxlArAl