《算法设计与分析基础》（Python语言描述） 课件 第4章分治法.pptx

第4章分而治之—分治法;分治从字面上的解释就是“分而治之”。

把一个复杂的问题分成k（1k≤n）个相同或相似的子问题，再把子问题分成更小的子问题，以此类推，直到可以直接求解为止，原问题的解可以通过子问题的解合并得到。;分治法求解问题的特征;分治算法的求解过程;1 defdivide-and-conquer(P): #分治算法框架

2 if|P|≤n0:returnadhoc(P)

3 将P分解为较小的子问题P1，P2，…，Pk

4 foriinrange(1,k+1): #循环处理k次

5 yi=divide-and-conquer(Pi) #递归解决Pi

6 returnmerge(y1，y2，…，yk) #合并子问题;【例4-1】给定一棵采用二叉链存储的二叉树b，设计一个算法求其中叶子结点的个数。;;;;;;;;;;;;;;;;;;;已知由n（n≥2）个正整数构成的集合A={ak}（0≤kn），将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C、C++描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;采用二分法求含有n个有序元素的序列a、b的中位数;（2）n1分为3种情况。;②若a[m1]b[m2]，则舍弃序列a中前半部分（较小的一半），同时舍弃序列b中后半部分（较大的一半）要求舍弃的长度相等。;③若a[m1]b[m2]，则舍弃序列a中后半部分（较大的一半），同时舍弃序列b中前半部分（较小的一半），要求舍弃的长度相等。舍弃一半即?n/2?个元素。;;;;;;;;;;;;4.1分治法概述;;;;;;;;问题描述：给定一个含n（1≤n≤10^5）个整数的数组?nums，设计一个算法找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

例如，nums={-2，1，-3，4，-1，2，1，-5，4}，答案为6，对应的连续子数组是{4，-1，2，1}。

要求设计如下方法：

def?maxSubArray(self,?nums:?List[int])?-?int;;;;;;;;;;;;问题描述：含n个整数数组nums（0≤n≤3000，-10^5≤nums[i]≤10^5）。设计一个算法判断nums中是否存在三个元素a，b，c，使得a+b+c=0成立。要求找出所有和为0且不重复的三元组。

例如，nums={-1，0，1，2，-1，-4}，结果为{{-1，-1，2}，{-1，0，1}}。

要求设计如下方法：

def?threeSum(self,?nums)?-?List[List[int]]:;;;;;;【问题描述】给定若干个二维空间中的点，点集采用数组p存放，任意两个不同点之间有一个直线距离，求最近的两个点的距离。;对p中所有点按x坐标递增排序，采用分治法策略求解。;;;;;