《算法設(shè)計(jì)與分析》課件 第4章 分治

算法設(shè)計(jì)與分析分治主要內(nèi)容分治的基本方法快速排序最大子數(shù)組問題最近點(diǎn)對(duì)問題尋找第k小元素棋盤覆蓋分治的思想規(guī)模比較大的問題分解成較小的問題，較小的問題再解決成更小的問題，直到容易解決為止對(duì)較小問題的解決，是繼續(xù)分解--遞歸方程直到容易解決為止（通常為1個(gè)元素）--邊界條件1合并排序（分治）52分解47分解13分解26分解5247分解1326分解52471326分解524713261合并排序（分治）25合并47合并13合并26合并2457合并1236合并12234567合并524713261合并排序（分治）首先對(duì)原數(shù)組分解成左右兩個(gè)子數(shù)組（減小問題的規(guī)模）（語句4-5）對(duì)這兩個(gè)子數(shù)組進(jìn)行排序，怎么排序？遞歸的調(diào)用原函數(shù)進(jìn)行排序即可（語句6-7）最后通過合并操作對(duì)排序后的子數(shù)組進(jìn)行合并（語句8）1分治步驟分解：將原問題分解成規(guī)模較小的子問題原問題P可以被分成多個(gè)子問題P1,P2,···,Pk子問題的形式需要和原問題一致解決：通過遞歸的方式解決子問題P1,P2的獨(dú)立解，以及P1,P2共同相關(guān)的解合并：對(duì)子問題的解進(jìn)行合并，形成原問題的解。1分治步驟原問題(sizen)子問題1子問題2子問題k…子問題21子問題22子問題2k…:分解:遞歸解決

:合并2快速排序快速排序的基本步驟2快速排序：分解主元的選擇：第一個(gè)元素或者最后一個(gè)元素問題：相同元素的位置發(fā)生了改變2快速排序：分解主讓i指向小于等于主元素部分的最后一個(gè)元素，j指向大于主元素部分的最后一個(gè)元素2快速排序2快速排序：復(fù)雜度分析對(duì)半分按比例分2快速排序：復(fù)雜度分析常數(shù)劃分算法期望復(fù)雜度3最大子數(shù)組問題3最大子數(shù)組問題最大子數(shù)組的基本步驟3最大子數(shù)組問題最大子數(shù)組的基本步驟3最大子數(shù)組問題橫跨在兩個(gè)子問題上的最大子數(shù)組只要依次遍歷左右數(shù)組的所有子數(shù)組，即可找到橫跨在兩個(gè)子問題上的最大子數(shù)組復(fù)雜度3最大子數(shù)組問題復(fù)雜度4最近點(diǎn)對(duì)問題窮舉求解將每一個(gè)點(diǎn)都與其它n-1個(gè)點(diǎn)的距離算出來，然后找出其中最小的即可4最近點(diǎn)對(duì)問題最近點(diǎn)對(duì)的基本步驟4最近點(diǎn)對(duì)問題最近點(diǎn)對(duì)的基本步驟4最近點(diǎn)對(duì)問題為此，我們?cè)O(shè)δ=min{δl,δr}，并在直線L左右兩邊分別畫出寬度為δ的區(qū)域，如圖中的Sl′和Sr′，顯而易見，小于min{δl,δr}的點(diǎn)對(duì)只可能出現(xiàn)在這個(gè)兩個(gè)區(qū)域。那么，是不是只要比較所有Sl′和Sr′間點(diǎn)對(duì)的距離即可4最近點(diǎn)對(duì)問題只需要比較圖中所示的δ?2δ長(zhǎng)方形上的點(diǎn)即可，落在這個(gè)長(zhǎng)方形外的點(diǎn)和p的距離一定是大于δ的。這個(gè)長(zhǎng)方形區(qū)域最多只能放6個(gè)點(diǎn)

哪6個(gè)點(diǎn)？在y軸上投影，相鄰的8個(gè)點(diǎn)

4最近點(diǎn)對(duì)問題復(fù)雜度還能不能進(jìn)一步降低？4最近點(diǎn)對(duì)問題復(fù)雜度4最近點(diǎn)對(duì)問題5尋找第k小元素5尋找第k小元素5尋找第k小元素如何將原數(shù)組分成兩個(gè)子問題？尋找一個(gè)中間元素如何找到這個(gè)處于中間位置的元素m？將n個(gè)元素劃分成m個(gè)組(通常是每組5個(gè)元素)，取每組的中間元素，再取這些中間元素的中間元素怎么找到中間元素的中間元素？遞歸調(diào)用5尋找第k小元素哪個(gè)子問題需要被舍棄？元素分成3組，小于m，等于m，和大于m，找到相應(yīng)的組，舍棄其他組一

為方便演示，設(shè)閾值為6?，F(xiàn)要尋找下面數(shù)組A中的第13小元素：A={8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7}{8,33,17,51,57}{49,35,11,25,37}{14,3,2,13,52}{12,6,29,32,54}{5,16,22,23,7}{8,17,33,51,57}{11,25,35,37,49}{2,3,13,14,52}{6,12,29,32,54}{5,7,16,22,23}M={33,35,13,29,16}mm=29A1={8,17,11,25,14,3,2,13,12,6,5,16,22,23,7}A2={29}A3={33,51,57,49,35,37,52,32,54}因?yàn)閗=13<|A1|=15{8,17,11,25,14}{3,2,13,12,6}{5,16,22,23,7}M={14,6,16}mm=14{8,11,14,17,25}{2,3,6,12,13}{5,7,16,22,23}A={8,17,11,25,14,3,2,13,12,6,5,16,22,23,7}A1={8,11,3,2,13,12,6,5,7}A2={14}A3={17,25,16,22,23}M={14,6,16}mm=14因?yàn)閗=13>|A1|+|A2|＝9＋1=10因?yàn)閨A3|<p=6閾值{16,17,22,23,25,}returnA[3]因?yàn)?3=13-9-1)5尋找第k小元素5尋找第k小元素：復(fù)雜度5尋找第k小元素：復(fù)雜度5尋找第k小元素：復(fù)雜度5尋