Chapter分而治之算法

1、 總的比較次數(shù)：總的比較次數(shù)：2n-3templatebool MinMax(T a , int n, int& Min, int& Max) if (n 1) return false; Min = Max = 0; for (int i = 1; i ai) Min = i; if (aMax ai) Max = i; return true;/程序程序2-27templatebool MinMax(T a , int n, int& Min, int& Max) if (n 1) return false; Min = Max = 0; for (int

2、i = 1; i ai) Min = i; else if (aMax ai) Max = i; return true;比較次數(shù)：比較次數(shù)：2n-2最多：最多：2n-2C(2)=1C(4)=4C(8)=10傳統(tǒng)方法：傳統(tǒng)方法：2n-3=13，n=8 采用二叉樹形式描述解空間采用二叉樹形式描述解空間 由根到葉進(jìn)行問題分解，由葉到根進(jìn)行問題解決由根到葉進(jìn)行問題分解，由葉到根進(jìn)行問題解決奇數(shù)比較次數(shù)：奇數(shù)比較次數(shù)：3*(n/2-1)偶數(shù)比較次數(shù)：偶數(shù)比較次數(shù)：3*(n/2-1)+1綜合：綜合：3n/2-21122kk1122kk1122kk1122kk00014112222000122231110

3、00122231111221630281016*206181221630281016*206181) 排序碼小于基準(zhǔn)排序碼小于基準(zhǔn)對象排序碼的對象對象排序碼的對象都移到序列左側(cè)；都移到序列左側(cè)；2) 基準(zhǔn)對象安放基準(zhǔn)對象安放到位。到位。)log() 1 () 1(log()(22nnOnTnnnT)()()(211nOinnTni 取取al、a(l+r)/2、ar中大小居中的元素作為支點中大小居中的元素作為支點 將中值元素和將中值元素和a1進(jìn)行交換，然后執(zhí)行進(jìn)行交換，然后執(zhí)行QuickSort 快速排序的應(yīng)用快速排序的應(yīng)用 選擇中值問題：首先對選擇中值問題：首先對n個元素進(jìn)行排序，然后個元素進(jìn)

4、行排序，然后取出取出ak-1中的元素，中的元素，k= n/2 【問題描述問題描述】給定給定n n個點個點(x(xi i,y,yi i)(1in)(1in)，要求，要求找出其中距離最近的兩個點。找出其中距離最近的兩個點。 直接方法：查找所有的直接方法：查找所有的n(n-1)/2n(n-1)/2對點，計算每一對點，計算每一對點的距離；時間復(fù)雜度對點的距離；時間復(fù)雜度(n(n2 2) )； 分而治之思想：分而治之思想： 設(shè)設(shè)d=min(dA, dB)，中值點，中值點(xm,ym) 第三類點的范圍限定：以分割線為第三類點的范圍限定：以分割線為中線，寬度為中線，寬度為2d；即查找所有滿足；即查找所有滿足

5、: |x-xm |d的點集的點集 由此限定，對由此限定，對A、B點集進(jìn)行篩選，點集進(jìn)行篩選，剩余點集即為第三類點剩余點集即為第三類點 考慮到比較的問題，可對所有點按考慮到比較的問題，可對所有點按照照x坐標(biāo)進(jìn)行升序排序！坐標(biāo)進(jìn)行升序排序！RA RBddxm 設(shè)設(shè)RA、RB分別代表分別代表A和和B中篩選剩余點集中篩選剩余點集 查找點對查找點對(p,q), dist(p,q)d, p RA , q RB 設(shè)設(shè)p的坐標(biāo)的坐標(biāo)(px, py) ，則查找這樣的，則查找這樣的q點，滿足：點，滿足：py-dqypy+d 考慮到比較的問題，可對所有點在按照考慮到比較的問題，可對所有點在按照x x坐標(biāo)進(jìn)坐標(biāo)進(jìn)行排序的基礎(chǔ)上，再按照行排序的基礎(chǔ)上，再按照y y坐標(biāo)進(jìn)行排序坐標(biāo)進(jìn)行排序 算法思想：從最小算法思想：從最小y y坐標(biāo)點開始，和后續(xù)頂點兩坐標(biāo)點開始，和后續(xù)頂點兩兩配對，判斷兩配對，判斷p py-qyd即可即