计算机算法基础 第2版 课件 第2章　分治法.pptx

1

第2章 分治法

分治法原理 2

递推关系求解 6

替换法 7

序列求和法和递归树法 10

主方法求解 12

3 例题示范 14

1.分治法原理

当输入规模很小时，问题都容易解。当规模很大时，一个基本方法就是把大规模问题转换为一组小规模问题去解。分治法是这种方法之一。

分治算法要讲明三件事：

底：对足够小的输入规模，如何直接解出。

分：如何将规模为n的输入分为一组规模小些的子问题。

每个子问题又要递归地分解为更小的子问题，直到底为止。被分解的原问题或子问题，称为那些由它分解得到的子问题的父问题。这里，父子关系就是分解和被分解的关系。

合： 如何从子问题的解中获得它们的父问题的解。

合是一个逐层向上的合并过程，直到最初的原问题得解为止。

2

3

一个例子：二元有哪些信誉好的足球投注网站

Binary-Search(A,p,r,x)

输入：任一段子序列，A[p]≤A[p+1]≤…≤A[r]，和要找的数字x。

输出:i如果序列中有A[i]=x，否则nil。

1 ifpr //表明数组为空集

2 thenreturn(nil)

3 endif

4 mid(p+r)/2

5 ifA[mid]=x

6 thenreturn(mid)

7 else ifxA[mid]

8 thenBinarySearch(A,p,mid-1,x)

9 elseBinarySearch(A,mid+1,r,x)

10 endif

11 endif

12 End

4

几点解释：

算法先找出序列的中位数A[mid]，mid=(p+r)/2。如果A[mid]=x，问题解决。否则，原序列一分为二，前一半为A[p..mid-1]，后一半为A[mid+1..r]。如果xA[mid]，则只需有哪些信誉好的足球投注网站前一半，否则有哪些信誉好的足球投注网站后一半。

每递归一步，有哪些信誉好的足球投注网站范围减半，伪码要适用于不同规模的子问题。所以，输入是A[p..r]，而不是A[1..n]。

解原问题时，要设计一个主程序来调用这个分治算法。例如，算法Binary-Search设计好之后，主程序需要调用Binary-Search(A,1,n,x)。

分治法只需说清楚如何把A[p..r]分解为A[p..mid-1]和A[mid+1..r]就可以了。

把A[p..mid-1]分为更小的子问题由编译软件自动完成。软件会动态地把r置为mid-1。这时，A[p..r]代表的是A[p..mid-1]。因此，算法只要说清楚如何分解A[p..r]就可以了，千万不要画蛇添足。

5

表示复杂度的递推关系

因为分治法含有递归调用，所以难以直接计算基本运算的次数。

为得到复杂度，先建立一个表示复杂度的递推关系，然后求解得到。

以二元有哪些信誉好的足球投注网站为例，A[1..n]中的数和x之间的比较是主要的基本运算。

假设在最坏情况下，二元有哪些信誉好的足球投注网站需要T(n)次比较，那么我们可以有以下的递推关系：

T(0)=0 （n=0时，不需比较）

T(n)=T(n/2)+1 （与x比较一次，再加上子问题需要的比较次数）

一般情况，把规模为n的输入分为规模为n/b(b为正整数)的一组子问题，然后解出其中a个子问题并从而获得原问题的解，通常有递推关系：

T(1)=c （c0，常数，底的复杂度）

T(n)=aT(n/b)+f(n) （f(n)是分解及合并所需的时间）

分治法的复杂度往往需要解以下的递推关系：

T(1)=c

T(n)=aT(n/b)+f(n)

主要方法：

替换法:

先猜想一个复杂度，然后用归纳法证明其正确。

序列求和法

从原递推关系逐步展开后得一序列，

然后对该序列求和后得解。

6

2.递推关系求解

7

解：先证T(n)=O(nlgn)，即存在c0，使得n2时，T(n)≤cnlgn。

归纳基础:

当n=2,3,4时，T(n)=(1)，故有c0使T(n)≤cnlgn。可假定c1。

归纳步骤:

假设当n=2,3,4,…,(k-1)时，T(n)≤cnlgn成立。当n=k(k≥5)时因为n/2=k/2≤k-1，由归纳假设得到

T(n/2)≤c(n/2)lg(n/2)≤c(n/2)lg(n/2)=(cn/2)(lgn-1)。

从而，从递推关系和c1得到：

T(n)=2T(n/2)+n≤2(