《算法设计与分析》课件 第4章 分治.pptx

算法设计与分析分治

主要内容分治的基本方法快速排序最大子数组问题最近点对问题寻找第k小元素棋盘覆盖

分治的思想规模比较大的问题分解成较小的问题，较小的问题再解决成更小的问题，直到容易解决为止对较小问题的解决，是继续分解--递归方程直到容易解决为止（通常为1个元素）--边界条件

1合并排序（分治）52分解47分解13分解26分解5247分解1326分解52471326分1合并排序（分治）25合并47合并13合并26合并2457合并1236合并12234567合1合并排序（分治）首先对原数组分解成左右两个子数组（减小问题的规模）（语句4-5）对这两个子数组进行排序，怎么排序？递归的调用原函数进行排序即可（语句6-7）最后通过合并操作对排序后的子数组进行合并（语句8）

1分治步骤分解：将原问题分解成规模较小的子问题原问题P可以被分成多个子问题P1,P2,···,Pk子问题的形式需要和原问题一致解决：通过递归的方式解决子问题P1,P2的独立解，以及P1,P2共同相关的解合并：对子问题的解进行合并，形成原问题的解。

1分治步骤原问题(sizen)子问题1子问题2子问题k…子问题21子问题22子问题2k…?:分解?:递归解决?:合并

2快速排序快速排序的基本步骤

2快速排序：分解主元的选择：第一个元素或者最后一个元素问题：相同元素的位置发生了改变

2快速排序：分解主让i指向小于等于主元素部分的最后一个元素，j指向大于主元素部分的最后一个元素

2快速排序

2快速排序：复杂度分析对半分按比例分

2快速排序：复杂度分析常数划分算法期望复杂度

3最大子数组问题

3最大子数组问题最大子数组的基本步骤

3最大子数组问题最大子数组的基本步骤

3最大子数组问题横跨在两个子问题上的最大子数组只要依次遍历左右数组的所有子数组，即可找到横跨在两个子问题上的最大子数组复杂度

3最大子数组问题复杂度

4最近点对问题穷举求解将每一个点都与其它n-1个点的距离算出来，然后找出其中最小的即可

4最近点对问题最近点对的基本步骤

4最近点对问题最近点对的基本步骤

4最近点对问题为此，我们设δ=min{δl,δr}，并在直线L左右两边分别画出宽度为δ的区域，如图中的Sl′和Sr′，显而易见，小于min{δl,δr}的点对只可能出现在这个两个区域。那么，是不是只要比较所有Sl′和Sr′间点对的距离即可

4最近点对问题只需要比较图中所示的δ?2δ长方形上的点即可，落在这个长方形外的点和p的距离一定是大于δ的。这个长方形区域最多只能放6个点哪6个点？在y轴上投影，相邻的8个点

4最近点对问题复杂度还能不能进一步降低？

4最近点对问题复杂度

4最近点对问题

5寻找第k小元素

5寻找第k小元素

5寻找第k小元素如何将原数组分成两个子问题？寻找一个中间元素如何找到这个处于中间位置的元素m？将n个元素划分成m个组(通常是每组5个元素)，取每组的中间元素，再取这些中间元素的中间元素怎么找到中间元素的中间元素？递归调用

5寻找第k小元素哪个子问题需要被舍弃？元素分成3组，小于m，等于m，和大于m，找到相应的组，舍弃其他组

一为方便演示，设阈值为6。现要寻找下面数组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}因为k=13|A1|=15{8,17,11,25,14}{3,2,13,12,6}{5