分治算法.ppt

分治算法1分治算法基本思想2典型二分法3二分法不相似情况4二分法不独立情况5非等分分治分治法1分治法的基本思想对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小),则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并,得到原问题的解。这种算法设计策略叫做分治法(divideandconquer)。分治法在每一层递归上由三个步骤组成:(1)划分(divide):将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题。(2)解决(conquer):若子问题规模较小,则直接求解;否则递归求解各子问题。(3)bine):将各子问题的解合并为原问题的解。它的一般算法设计范型如下:DIVIDE&CONQUER(P)1if|P|≤c2thenreturn(DSOLVE(P))3elsedividePintokintoP1,P2,…,Pksubproblems4fori←1tok5dosi←DIVIDE&CONQUER(Pi)BINE(s1,s2,…,sk)7returnS从分治法的一般设计模式可以看出,直接用它设计出的算法是一个递归算法。我们可用递归方程描述递归算法的运行时间。设T(n)表示用分治法求解规模为n的问题所需的计算时间,如果问题规模足够小,比如n≤c,则可直接求解问题,T(n)=Θ(1)。假定将原问题分为k个子问题,每一个子问题规模是原问题的1/m,若分解该问题和合并该问题的时间分别为D(n)和C(n),则算法的计算时间T(n)可表示为如下的递归方程:>c如果n为m的幂,分解该问题和合并该问题的时间为f(n),则该递归方程的解为子问题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所在位置,算法终止;如果v<A([n/2]),则在数组的左半部分继续查找v;如果v>A([n/2]),则在数组的右半部分继续查找v。当所查找的区间为0时,表示v不在数组中,返回查找不成功标志0。算法ITERATIVEBINARYSEARCH描述了上述思想。ITERATIVEBINARYSEARCH(A,v,low,high)1whilelow≤high2domid←[(low+high)/2]3ifv=A[mid]4thenreturnmid5elseifv>A[mid]6thenlow←mid+17elsehigh←mid-18returnNIL算法第1行检查待查找的区间,第2行计算待比较的元素位置。如果第3行中的D条件为真,则表示查找成功,返回元素所在位置;否则,或者在左半部分继续进行查找(执行第6行),或者在右半部分进行查找(执行第7行)。如果第1行的while循环条件为假,则执行第8行,返回查找不成功标志0。算法ITERATIVEBINARYSEARCH在运行过程中,维持以下循环不变式:如果待查找的元素在数组中,则待查找元素必然在子数组中。