《算法201003-分治1》由会员分享，可在线阅读，更多相关《算法201003-分治1（26页珍藏版）》请在金锄头文库上搜索。
1、第2章 分治与递归算法（1）1 分治与递归算法的基本思路2 二分查找问题的分治与递归算法 Divide and Conquer 1次品的甄别2 循环赛赛程制定两个例子在n个乒乓球中有1个次品,外表和正品一样,但重量不同,不知道是轻是重, 试给出一个算法,用不带砝码的天平以尽可能少的次数将次品挑出来.有n支球队参加循环赛，设计一个满足下面要求的比赛日程表： （1)每支球队必须与其他n-1支球队各赛一次； （2)每支球队一天只能比赛一次； （3)当n为偶数时，比赛进行n-1天；当n为奇数时，比赛进行n天。3 网络淘宝 分布式查询 4 云数据中心 （阿里云） 2.1 分治法的一般方法问题(N个输入)
2、子问题1子问题2子问题k子问题1子问题2子问题k相同的 类型不用再分就可求解合并分治法的适用条件n分治法所能解决的问题一般具有以下几个特 征： 1、该问题的规模缩小到一定的程度就可以容 易地解决； 2、该问题可以分解为若干个规模较小的相同 问题，即该问题具有最优子结构性质。 3 、用该问题分解出的子问题的解可以合并为 该问题的解； 4、该问题所分解出的各个子问题是相互独立 的，即子问题之间不包含公共的子子问题。 分治策略DANDC的抽象化控制Procedure DANDC(p,q)global n,A(1:n);integer m,p,q;/1pqn/if SMALL(p,q)then ret
3、urn(G(p,q)else mDIVIDE(p,q)/pmq/return(COMBINE(DANDC(p,m),DANDC(m+1,q) )endif End DANDC判断输入规模q-p+1是否足够的小求解该规模问题解的函数将两个子问题的解合成原问题分割函数分治策略DANDC的计算时间n倘若所分成的两个子问题的输入规模大致相等 ，则分治策略DANDC的计算时间可表示为：T(n)=g(n)n足够小2T(n/2)+f(n)否则说明：T(n)是输入规模为n的分治策略的计算时间 g(n)是对足够小的输入规模能直接计算出答案的时间 f(n)是COMBINE解合成原问题的计算时间2.2 二分查找n问
4、题描述n已知一个按非降次序排列的元素表 a1,a2,an，判定某个给定元素x是否在该 表中出现，若是，则找出该元素在表中的位 置，并置于j，否则，置j为0。n一般解决方法（从头到尾查找一遍）a1a2a3a4anx 成功和不成功的平均计算时间都是n二分查找原理将问题表示为：I=(n,a1,an,x) 选取一个下标k，可得到三个子问题：nI1=(k-1,a1,ak-1,x)nI2=(1,ak,x)nI3=(n-k,ak+1,an,x)如果对所求解的问题（或子问题）所选的下标 k都是中间元素的下标，k=(n+1)/2，则由 此产生的算法就是二分查找算法。二分查找算法Procedure BINSRCH
5、(A,n,x,j)integer low,high,mid,j,n;low1;highnif(n0)while （lowhigh） do mid(low+high)/2 /*取中间值*/casexAmid: lowmid+1 /*寻找后一半*/else: jmid ; return /*查找成功*/endcasej0 /*查找失败*/ End BINSRCH二分查找算法实例 假设在数组A(1:9)中顺序放了以下9个元素 ：-15 , -6 , 0 , 7 , 9 , 23 , 54 , 82 , 101 要求查找的x分别为：101 , -14 , 82X=101 Lowhigh mid 195
6、 697 898 999 OKX=-14 Lowhigh mid 195 142 1112 1NOX=82 Lowhigh mid 195 697 898OK二分查找算法正确性的证明证明算法是否正确n如果n=0，则不进入循环，j=0，算法终止n否则就会进入循环与数组A中的元素进行比较n如果x=Amid，则j=mid，查找成功，算法终止n否则，若xA(mid)，则缩小到A(mid+1)和A(n)之间查找n按上述方式缩小查找区总可以在有限步内使lowhighn如果出现这种情况，说明x不在A中，j=0，算法终止二分查找算法所需的空间和时间n所需空间n用n个位置存放数组A，还有low,high,mid
7、,x,j 五个变量需要存储，n共需空间n+5n计算时间n对于计算时间，需要分别考虑以下几种情况：n成功查找的最好情况和不成功查找的最好情况n成功查找的平均情况和不成功查找的平均情况n成功查找的最坏情况和不成功查找的最坏情况成功查找最好情况和不成功查找最好情况n成功的查找共有n种n不成功的查找共有n+1种A(1)(2)(3)(4)(5)(6)(7)(8)(9)元素-15-6079235482101 比较次 数323413234 3334433344不成功的查找成功的查找二元比较树572134689内结点,表示 一次元素的 比较,存放一 个mid值外结点,表示 不成功查找的 一种情况每一条路径表
8、示一个元素的 比较序列9-6-1505472382101思考：如何 构造一个序 列的二元比 较树？二分查找的时间复杂度n定理2.2 ：若n在区域2k-1,2k)中，则对于一次成 功的查找，二分查找至多作k次比较，至少作1次 比较；而对于一次不成功的查找，或者作k-1次比 较或者作k次比较。深度为k的二叉树的最大结点数为2k-1二分查找在各种情况下的查找时间计计算时间时间最好平均最坏成功的查查找(1)(logn)(logn)不成功的查查找(logn)(logn)(logn)问题：是否存在一种以比较为基础的算法，其最 坏情况时间可能低于O(logn)，也就是存在其最 坏情况时间比二分查找数量级还低
9、的算法？以比较为基础查找的时间下界n有n个如下关系的元素:A(1)A(2)A(n), 查找一给定元素X是否在A中出现X:A(1)X:A(2)X:A(n)不成功不成功不成功不成功线性查找二分查找X:A(n+1)/2)X:A(3n+1)/4)X:A(n+1)/4)X:A(n)X:A(2n+1)/2+1)X:A(2n+1)/2-1)X:A(1)不成功不成功不成功不成功不成功不成功不成功不成功以比较为基础查找的时间下界n定理2.3 ：设A(1:n)含有n(n1)个不同的元素，排序 为A(1)A(2)A(n)。又设以比较为基础去判断 是否xA(1:n)的任何算法在最坏情况下所需的最小比 较次数是FIND
10、(n)，那么FIND(n)log(n+1)。 证明： FIND(n)不大于树中由根到一个叶子结点的最长路径的距离;所有树中必有n个内结点与x在A中可能出现的情况相对应;若一个二元树的所有内结点的级数小于或等于k，则最多2k-1个内结点，n 2k-1,即FIND(n)=klog(n+1)。定理表明，任何一种以比较为基础的算法，其 最坏情况时间都不可能低于O(logn)，也就是不 可能存在其最坏情况时间比二分查找数量级还 低的算法。二元比较树可以表示基于比较的查找计算an =?分治法的复杂度分析(1)设将原问题分解为k个规模为n/k的子问题，且分解原问题并将子问题的解 进行合并得到原问题的解需要的时间为f(n)，T(n)表示利用分治法求解该问题 的时间复杂性，则(2)更一般情况下其中a,b为已知常数，T(1)已知，并且n为b的幂。利用替换法设a=2,b=2. 令T(1)=2,f(n)=n。则对a,b用替换法，可以得到a=2,b=2.h(n)u(n)不同h(n)对应的u(n)值（查表求值）举例1） 当n为2的幂时，对比得到： a=1,b=2,f(n)=c作业21 利用替换法考虑如下T(n)的时间复杂度：2 P512.2 ,2.3
