分治算法

分治算法1分治算法基本思想2典型二分法3二分法不相似情况4二分法不独立情况5非等分分治分治法1分治法的基本思想对于一个规模为n的问题，若该问题可以容易地解决(比如说规模n较小)，则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并，得到原问题的解。这种算法设计策略叫做分治法(divideandconquer)。分治法在每一层递归上由三个步骤组成：(1)划分(divide)：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题。(2)解决(conquer)：若子问题规模较小，则直接求解；否则递归求解各子问题。(3)合并(combine)：将各子问题的解合并为原问题的解。它的一般算法设计范型如下：DIVIDE&CONQUER(P)1if|P|≤c2thenreturn(DSOLVE(P))3elsedividePintokintoP1,P2,…,Pksubproblems4fori←1tok5dosi←DIVIDE&CONQUER(Pi)6S←COMBINE(s1,s2,…,sk)7returnS从分治法的一般设计模式可以看出，直接用它设计出的算法是一个递归算法。我们可用递归方程描述递归算法的运行时间。设T(n)表示用分治法求解规模为n的问题所需的计算时间，如果问题规模足够小，比如n≤c，则可直接求解问题，T(n)=Θ(1)。假定将原问题分为k个子问题，每一个子问题规模是原问题的1/m，若分解该问题和合并该问题的时间分别为D(n)和C(n)，则算法的计算时间T(n)可表示为如下的递归方程：)()()/()1(Θ)(nCnDmnkTnTn≤cnc如果n为m的幂，分解该问题和合并该问题的时间为f(n)，则该递归方程的解为1log0log)/()(niiikmmmnfknnT子问题2的解子问题2的解原始问题的解原始问题的规模是n子问题1的规模是n/2子问题2的规模是n/22典型二分法不同于现实中对问题（或工作）的分解，可能会考虑问题（或工作）的重点、难点、承担人员的能力等来进行问题的分解和分配。在算法设计中每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时，称为二分法。二分法是分治法较常用的分解策略，数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的。1二叉查找算法已知一个按照非降序排列的n个元素列表a1，a2，…，an，要求判定某个给定元素v是否在该表中出现。如果元素v在表中出现，则找出v在表中的位置，表示查找成功；否则返回位置0，表示查找不成功。二叉查找(binarysearch)算法的基本思想是将n个元素分成大致相等的两部分，取A(［n/2］)与v进行比较，如果相等，则找到v，返回v所在位置，算法终止；如果vA(［n/2］)，则在数组的左半部分继续查找v；如果vA(［n/2］)，则在数组的右半部分继续查找v。当所查找的区间为0时，表示v不在数组中，返回查找不成功标志0。算法ITERATIVEBINARYSEARCH描述了上述思想。ITERATIVEBINARYSEARCH(A,v,low,high)1whilelow≤high2domid←［(low+high)/2］3ifv=A［mid］4thenreturnmid5elseifvA［mid］6thenlow←mid+17elsehigh←mid-18returnNIL算法第1行检查待查找的区间，第2行计算待比较的元素位置。如果第3行中的Ｄ条件为真，则表示查找成功，返回元素所在位置；否则，或者在左半部分继续进行查找(执行第6行)，或者在右半部分进行查找(执行第7行)。如果第1行的while循环条件为假，则执行第8行，返回查找不成功标志0。算法ITERATIVEBINARYSEARCH在运行过程中，维持以下循环不变式：如果待查找的元素在数组中，则待查找元素必然在子数组中。在循环迭代开始时，子数组为输入原数组，循环不变式为真。在随后的各循环迭代步中，下一迭代步中是当前子数组中去掉不含v的那半部分数组后所剩余的部分，如果v在原数组中，则v必在下一迭代步中将要查找的子数组中，因此，在每一循环步中，不变式总为真。在每次迭代中，当A［mid］=v时，将返回下标mid；否则，子数组长度将减少一半多。因为原数组有有限个元素，循环必定在有限步内终止。因而，若算法终止于while循环(第4行)，则返回下标mid，循环不变式为真。若算法在第8行终止，则返回NIL，即待查找的元素不在原数组中。图二叉判定树(n=12)7255892344637125438010312459781011126为了理解二叉查找算法的运行过程，我们把它的执行想象成一棵二叉判定树(binarydecisiontree)的执行。下面以A=〈5，7，12，25，34，37，43，46，58，80，92，105〉为例来说明，如图2-6所示(图中n=12)。树中每一个结点表示一个元素在数组中的位置，也是算法运行过程中所有可能的mid值，结点外面的数值表示该元素的值。算法中所做的第一个元素比较是与A［6］进行的比较，如果待查找元素比A［6］小，则算法沿着左子树与A［3］比较；如果待查找元素比A［6］大，则算法沿着右子树与A［9］比较。通常称这种表示查找过程的二叉树为判定树。从判定树可见，查找元素25的过程恰好是走了一条从根结点到结点4的路径，和给定值25进行比较的元素个数为该路径上的结点数或结点4在判定树上的层数。因而，找到数组中任一元素的过程就是走了一条从根结点到该元素的路径，和给定值比较的元素个数恰为该结点在判定树上的层数。因此，二叉查找在查找成功时进行比较的元素个数最多不超过树的深度，而具有n个结点的判定树深度为［lbn］+1，所以，二叉查找在查找成功时进行比较的元素个数至多为［lbn］+1。如果在所有结点的空指针域上增加一个指向方形结点的指针，并称这些方形结点为判定树的外部结点，其中的数值表示待查找的元素可能值的范围，如58~80表示待查找的元素值在(58，80)之内，如图2-7所示，那么，二叉查找不成功的过程就是走了一条从根结点到外部结点的路径，和给定值进行比较的元素个数等于该路径上内部结点的个数，例如查找50的过程即为走了一条从根结点到结点46~58的过程。因此，二叉查找不成功时和给定元素比较的元素个数也至多为［lbn］+1。图2加上外部结点的二叉判定树＜572558923446371254380106312497115～77～1212～255837～43101225～3434～3743～4646～5858～8080～9292～105＞105假定在A中查找元素25、50，这分别是一次成功和一次不成功的查找。表2-1给出算法执行时变量low，high和mid的值。由表2-1可以得出，查找25进行3次元素比较，查找成功，返回元素在数组中的位置4。查找50进行4次元素比较，查找不成功，返回NIL。表1变量low，high和mid的运行轨迹我们对上述实例作进一步分析。如果以元素比较作为衡量算法的运行效率，由图1可知，查找12个元素中的每一个元素所需的比较次数如表2所示。表2元素的比较次数要找到一个元素至少要比较1次，至多比较4次。对找到所有12项的比较次数取平均值，可得到每一次成功查找的比较次数为37/12≈3.08。不成功查找的终止方式取决于v的值，总共有13种可能的情况，即vA［1］，A［1］vA［2］，A［2］vA［3］，A［3］vA［4］A［4］vA［5］，A［5］vA［6］，A［6］vA［7］，A［7］vA［8］A［8］vA［9］，A［9］vA［10］，A［10］vA［11］，A［11］vA［12］因此，一次不成功查找元素所需的比较次数为77.3134444443443443假定有序表的长度为n=2h-1，则二叉查找判定树是深度为h的满二叉树。树的第i层有2i-1个结点。假设数组中每个元素的查找概率相等(Pi=1/n)，则查找成功时，二叉查找的平均查找长度ASL(AverageSearchLength)为1)1(b1121ASL111nnnjnCPhjjniii因此，ASL=O(lbn)。由此可见，二叉查找的效率比顺序查找高，但二叉查找只适用于有序表，且限于顺序存储结构。3分治法应用实例1找最大值与最小值在含有n个不同元素的集合中同时找出它的最大值和最小值(maximum&minimum)的最简单方法是将元素逐个进行比较。算法中用max和min分别表示最大值和最小值。算法描述如下：MAXMIN(A)1max←min←A［1］2fori←2ton3doifA［i］max4thenmax←A［i］5elseifA［i］min6thenmin←A［i］7returnmax&min如果数组中元素按照递增的次序排列，则找出最大值和最小值所需的元素比较次数为n-1，这是最佳的情况。如果数组中元素按照递减的次序排列，则找出最大值和最小值所需的元素比较次数为2(n-1)，这是最坏情况。在平均情况下，A中将有一半元素使得第3行的比较为真，找出最大值和最小值所需的元素比较次数为3(n-1)/2。如果我们将分治策略用于此问题，每次将问题分成大致相等的两部分，分别在这两部分中找出最大值与最小值，再将这两个子问题的解组合成原问题的解，就可得到该问题的分治算法。算法描述如下：REC-MAXMIN(i，j，fmax，fmin)1ifi=j2thenfmax←fmin←A［i］3ifi=(j-1)4thenifA［i］A［j］5thenfmax←A［i］6fmin←A［j］7elsefmax←A［j］8fmin←A［i］9elsemid←［(i+j)/2］10REC-MAXMIN(i，mid，gmax，gmin)11REC-MAXMIN(mid+1，j，hmax，hmin)12fmax←max{gmax，hmax}13fmin←min{gmin，hmin}设T(n)表示算法所需的元素比较次数，则可得算法的递归方程为2)2/()2/(10)(nTnTnTn=1n=2n2假设n为2的幂，化简T(n)可得2)2/(10)(nTnTn=1n=2n2T(n)=2T(n/2)+2=2(2T(n/4)+2)+2=4T(n/4)+4+2……=2k-1T(2)+=2k-1+2k-2=3n/2-2112kii这表明算法的最坏、平均以及最好情况的元素比较次数为3n/2-2。事实上，至多进行3［n/2］次比较是找出最小值和最大值的充分条件。策略是维持到目前为止找到的最小值和最大值。我们并不将每个元素与最大值和最小值都进行比较，因为这样每个元素需要进行两次比较。下面我们成对处理元素。首先，输入元素成对相互进行比较，并将较小者与当前最小值比较，较大者与当前最大值比较。这样每两个元素进行三次比较。设置当前最小元素和最大元素的初始值，与n的奇偶性有关。当n为奇数时，我们将最小值和最大值都设为第一个元素，然后，将其余元素成对处理；当n为偶数时，我们在前两个元素之间进行一次比较，决定最大值和最小值的初始值，然后，将其余元素成对处理。以下分析上述算法的比较次数。如果n为奇数，那么需进行3［n/2］次比较；如果n为偶数，我们首先在前两个元素之间进行一次比较，然后进行3(n-2)/2次比较，总共进行3n/2-2次比较。因此，不论在哪一种情况下，比较的次数至多为3［n/2］可以证明，任何基于比较的找最大值和最小值的算法，其元素比较次数下界为［3n/2］-2［18］。在这种意义下，算法REC-MAXMIN是最优的。但是REC-MAXMIN也有其不足之处，它所要求的存储空间较大，即算法中的每次递归调用都需要保留i，j，fmax，fmin的值及返回地址