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 采用二叉樹(shù)形式描述解空間采用二叉樹(shù)形式描述解空間 由根到葉進(jìn)行問(wèn)題分解，由葉到根進(jìn)行問(wèn)題解決由根到葉進(jìn)行問(wèn)題分解，由葉到根進(jìn)行問(wè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)對(duì)象排序碼的對(duì)象對(duì)象排序碼的對(duì)象都移到序列左側(cè)；都移到序列左側(cè)；2) 基準(zhǔn)對(duì)象安放基準(zhǔn)對(duì)象安放到位。到位。)log() 1 () 1(log()(22nnOnTnnnT)()()(211nOinnTni 取取al、a(l+r)/2、ar中大小居中的元素作為支點(diǎn)中大小居中的元素作為支點(diǎn) 將中值元素和將中值元素和a1進(jìn)行交換，然后執(zhí)行進(jìn)行交換，然后執(zhí)行QuickSort 快速排序的應(yīng)用快速排序的應(yīng)用 選擇中值問(wèn)題：首先對(duì)選擇中值問(wèn)題：首先對(duì)n個(gè)元素進(jìn)行排序，然后個(gè)元素進(jìn)

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

5、: |x-xm |d的點(diǎn)集的點(diǎn)集 由此限定，對(duì)由此限定，對(duì)A、B點(diǎn)集進(jìn)行篩選，點(diǎn)集進(jìn)行篩選，剩余點(diǎn)集即為第三類(lèi)點(diǎn)剩余點(diǎn)集即為第三類(lèi)點(diǎn) 考慮到比較的問(wèn)題，可對(duì)所有點(diǎn)按考慮到比較的問(wèn)題，可對(duì)所有點(diǎn)按照照x坐標(biāo)進(jìn)行升序排序！坐標(biāo)進(jìn)行升序排序！RA RBddxm 設(shè)設(shè)RA、RB分別代表分別代表A和和B中篩選剩余點(diǎn)集中篩選剩余點(diǎn)集 查找點(diǎn)對(duì)查找點(diǎn)對(duì)(p,q), dist(p,q)d, p RA , q RB 設(shè)設(shè)p的坐標(biāo)的坐標(biāo)(px, py) ，則查找這樣的，則查找這樣的q點(diǎn)，滿足：點(diǎn)，滿足：py-dqypy+d 考慮到比較的問(wèn)題，可對(duì)所有點(diǎn)在按照考慮到比較的問(wèn)題，可對(duì)所有點(diǎn)在按照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)點(diǎn)開(kāi)始，和后續(xù)頂點(diǎn)兩坐標(biāo)點(diǎn)開(kāi)始，和后續(xù)頂點(diǎn)兩兩配對(duì)，判斷兩配對(duì)，判斷p py-qyd即可即