Chapter分而治之算法

1、 总的比较次数：总的比较次数：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;比较次数：比较次数：2n-2最多：最多：2n-2C(2)=1C(4)=4C(8)=10传统方法：传统方法：2n-3=13，n=8 采用二叉树形式描述解空间采用二叉树形式描述解空间 由根到叶进行问题分解，由叶到根进行问题解决由根到叶进行问题分解，由叶到根进行问题解决奇数比较次数：奇数比较次数：3*(n/2-1)偶数比较次数：偶数比较次数：3*(n/2-1)+1综合：综合：3n/2-21122kk1122kk1122kk1122kk00014112222000122231110

3、00122231111221630281016*206181221630281016*206181) 排序码小于基准排序码小于基准对象排序码的对象对象排序码的对象都移到序列左侧；都移到序列左侧；2) 基准对象安放基准对象安放到位。到位。)log() 1 () 1(log()(22nnOnTnnnT)()()(211nOinnTni 取取al、a(l+r)/2、ar中大小居中的元素作为支点中大小居中的元素作为支点 将中值元素和将中值元素和a1进行交换，然后执行进行交换，然后执行QuickSort 快速排序的应用快速排序的应用 选择中值问题：首先对选择中值问题：首先对n个元素进行排序，然后个元素进

4、行排序，然后取出取出ak-1中的元素，中的元素，k= n/2 【问题描述问题描述】给定给定n n个点个点(x(xi i,y,yi i)(1in)(1in)，要求，要求找出其中距离最近的两个点。找出其中距离最近的两个点。 直接方法：查找所有的直接方法：查找所有的n(n-1)/2n(n-1)/2对点，计算每一对点，计算每一对点的距离；时间复杂度对点的距离；时间复杂度(n(n2 2) )； 分而治之思想：分而治之思想： 设设d=min(dA, dB)，中值点，中值点(xm,ym) 第三类点的范围限定：以分割线为第三类点的范围限定：以分割线为中线，宽度为中线，宽度为2d；即查找所有满足；即查找所有满足

5、: |x-xm |d的点集的点集 由此限定，对由此限定，对A、B点集进行筛选，点集进行筛选，剩余点集即为第三类点剩余点集即为第三类点 考虑到比较的问题，可对所有点按考虑到比较的问题，可对所有点按照照x坐标进行升序排序！坐标进行升序排序！RA RBddxm 设设RA、RB分别代表分别代表A和和B中筛选剩余点集中筛选剩余点集 查找点对查找点对(p,q), dist(p,q)d, p RA , q RB 设设p的坐标的坐标(px, py) ，则查找这样的，则查找这样的q点，满足：点，满足：py-dqypy+d 考虑到比较的问题，可对所有点在按照考虑到比较的问题，可对所有点在按照x x坐标进坐标进行排序的基础上，再按照行排序的基础上，再按照y y坐标进行排序坐标进行排序 算法思想：从最小算法思想：从最小y y坐标点开始，和后续顶点两坐标点开始，和后续顶点两两配对，判断两配对，判断p py-qyd即可即