第2部分 算法设计策略 第5章 分治法 2019/4/5

5.2 求最大最小元 5.1 分治法的基本思想 5.3 二分搜索 5.4 排序问题 5.5 选择问题 5.6 斯特拉森矩阵乘法 5.2 求最大最小元 5.1 分治法的基本思想 5.3 二分搜索 5.4 排序问题 5.5 选择问题 5.6 斯特拉森矩阵乘法 2019/4/5

5.2 求最大最小元 2019/4/5

在一个元素集合L中寻找最大元素和最小元素的问题。 一般方法？ 2019/4/5

5.2.1 分治法求解 【程序5－4】 求最大最小元 template <class T> 5.2.1  分治法求解 【程序5－4】 求最大最小元 template <class T> void SortableList<T>::MaxMin(T& max, T& min)const { if (n==0)return; max=min=l[0]; for (int i=1; i<n; i++) { if(l[i]>max) max=l[i]; if(l[i]<min) min=l[i]; } 时间复杂度？ 2019/4/5

template <class T> 【程序5－5】分治法求最大最小元 template <class T> void SortableList<T>::MaxMin(int i, int j, T& max, T& min) const { T min1,max1; if (i==j) max=min=l[i]; else if (i==j-1) //只有两个元素时 if (l[i]<l[j]) { max=l[j]; min=l[i]; } else { max=l[i]; min=l[j]; 2019/4/5

if (max<max1) max=max1; if (min>min1) min=min1; } else { int m=(i+j)/2; MaxMin(i,m,max,min); MaxMin(m+1,j,max1,min1); if (max<max1) max=max1; if (min>min1) min=min1; } 2019/4/5

5.2.2 时间分析 定理5－2 设有n个元素的表，假定n是2的幂，即n=2k，k是正整数，程序5－5在最好、平均和最坏情况下的比较次数都为3n/2–2。 设n=2k，易解 2019/4/5

5.1 一般方法 2019/4/5

5.1.1 分治法的基本思想 分治法顾名思义就是分而治之。一个问题能够用分治法求解的要素是：第一，问题能够按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；第二，子问题足够小时可以直接求解；第三，能够将子问题的解组合成原问题的解。由于分治法要求分解成同类子问题，并允许不断分解，使问题规模逐步减小，最终可用已知的方法求解足够小的问题，因此，分治法求解很自然导致一个递归算法。 2019/4/5

SolutionType DandC(ProblemType P) { ProblemType P1，P2，，Pk; 【程序5-1】 分治法 SolutionType DandC(ProblemType P) { ProblemType P1，P2，，Pk; if (Small(P)) return S(P); else { Divide(P，P1，P2，，Pk); Return Combine(DandC(P1)， DandC(P2)，…，DandC(Pk)); } 2019/4/5

SolutionType DandC(int left，int right) { if (Small(left, right)) 【程序5-2】 一分为二的分治法 SolutionType DandC(int left，int right) { if (Small(left, right)) return S(left,right); else { int m=Divide(left，right); Return Combine(DandC(left，m)， DandC(m+1，right)); } 2019/4/5

T(n) = aT(n/b) + cnk，T(1) = c 5.1.2 算法分析 采用分治法求解问题通常得到一个递归算法。如果较大的问题被分解成同样大小的几部分，那么分析相应算法的执行时间，往往可得到如下的递推关系式： T(n) = aT(n/b) + cnk，T(1) = c 2019/4/5

定理5-1 设a,b,c和k为常数，T(n)=aT(n/b)+cnk，T(1)=c，则， 2019/4/5

n=bm 2019/4/5

设r= bk /a ，下面分三种情况计算 。 （1）若r<1，则 所以 （2）若r=1，则 （3）若r>1，则 2019/4/5

5.1.3 排序问题 数据结构 【程序5－3】 可排序表类 template <class K,class D> 5.1.3  排序问题 数据结构 【程序5－3】 可排序表类 template <class K,class D> struct E { //可排序表中元素的类型 operator K( )const { return key;} K key; D data; }; 2019/4/5

template <class T> class SortableList { //可排序表类 public: SortableList(int mSize); ~SortableList();  private: T *l ; //指向动态生成的一位数组 int maxSize; int n; }; 2019/4/5

5.3 二分搜索 2019/4/5

问题 在有序表（已按关键字值非减排序）中搜索给定元素的问题。 a0 am-1 am am+1 an-2 an-1 … 2019/4/5

5.3.1 分治法求解 int SortableList<T>::BSearch(const T& x, 5.3.1  分治法求解 int SortableList<T>::BSearch(const T& x, int left,int right)const 说明: 在范围为[left,right]的表中搜索与x有相同关键字值的元素；如果存在该元素，则函数返回该元素在表中的位置，否则函数返回－1，表示搜索失败。 2019/4/5

template <class T> 【程序5－6】二分搜索算法框架 template <class T> int SortableList<T>::BSearch(const T& x, int left,int right)const { if (left<=right){ int m=Divide(left+right); if (x<l[m]) return BSearch(x,left,m-1); else if (x>l[m]) return BSearch(x,m+1,right); else return m; } return -1; 2019/4/5

5.3.2 对半搜索 对半搜索 对半搜索是一种二分搜索。设当前搜索的子表 为（aleft,aleft+1,…,aright）， 令 5.3.2  对半搜索 对半搜索 对半搜索是一种二分搜索。设当前搜索的子表 为（aleft,aleft+1,…,aright）， 令 m=(left+right)/2 2019/4/5

template <class T> 【程序5－7】 对半搜索递归算法 template <class T> int SortableList<T>::BSearch(const T& x, int left, int right)const { if (left<=right){ int m=(left+right)/2; if (x<l[m]) return BSearch(x,left,m-1); else if (x>l[m]) return BSearch(x,m+1,right); else return m; } return -1; 2019/4/5

对于n0，程序5－7的对半搜索递归函数BSearch是正确的。 定理5－3 对于n0，程序5－7的对半搜索递归函数BSearch是正确的。 程序5-7是尾递归函数，易改为迭代形式 参考程序5-8 2019/4/5

template <class T> //程序5-8：对半搜索的迭代算法 template <class T> int SortableList<T>::BSearch1(const T& x)const { int m, left=0, right=n-1; while (left<=right){ m=(left+right)/2; if (x<l[m]) right=m-1; else if (x>l[m]) left=m+1; else return m; //搜索成功 } return-1; //搜索失败 2019/4/5

5.3.3  二叉判定树 二分搜索过程的算法行为可以用一棵二叉树来描述。通常称这棵描述搜索算法执行过程的二叉树为二叉判定树(binary decision tree)。 2019/4/5

如何构建二叉判定树 内节点 外节点 2019/4/5

具有n个内结点的对半搜索二叉判定树的左子树上有(n-1)/2个内结点，右子树上有n/2个内结点。 性质 5－1 具有n个内结点的对半搜索二叉判定树的左子树上有(n-1)/2个内结点，右子树上有n/2个内结点。 性质5－2 具有n(n>0）个内结点的二叉判定树的高度为log n+1 （不计外结点）。 2019/4/5

若n=2h-1，则对半搜索二叉判定树是满二叉树。 性质5－4 性质 5－3 若n=2h-1，则对半搜索二叉判定树是满二叉树。 性质5－4 若n=2h-1，则对半搜索二叉判定树的外结点均在h+1层上，否则，在第h或h+1层上，h=log n+1。 2019/4/5

对半搜索算法在搜索成功时的平均时间复杂度为(log n)。 定理 5－4 对半搜索算法在成功搜索的情况下，关键字值之间的比较次数不超过log n+1。对于不成功的搜索，算法需要作log n或log n+1次比较。 定理5－5 对半搜索算法在搜索成功时的平均时间复杂度为(log n)。 对半搜索是一个最优算法 2019/4/5

5.3.4 搜索算法的时间下界 定理5－6 在一个有n个元素的集合中，通过关键字值之间的比较，搜索指定关键字值的元素，任意这样的算法在最坏情况下至少需要作log n+1次比较。 2019/4/5

练习1 编写程序实现三分搜索算法，分析其时间复杂度，并与对半搜索算法的时间性能进行比较。 2019/4/5

5.4 排序问题 2019/4/5

问题 排序是将一个元素序列调整为按指定关键字值的递增（或递减）次序排列的有序序列。 2019/4/5

5.4.1  合并排序 合并两个有序序列 两路合并排序的基本运算是把两个有序序列合并成一个有序序列。 2019/4/5

时间复杂度分析？ 【程序5－9】 Merge函数 template <class T> void SortableList<T>::Merge(int left, int mid,int right) { T* temp=new T[right-left+1]; int i=left,j=mid+1,k=0; while (( i<=mid )&& (j<=right)) if (l[i]<=l[j]) temp[k++]=l[i++]; else temp[k++]=l[j++]; while (i<=mid) temp[k++]=l[i++]; while (j<=right) temp[k++]=l[j++]; for (i=0,k=left;k<=right;) l[k++] = temp[i++]; } 时间复杂度分析？ 2019/4/5

2019/4/5

---合并排序 分治法求解 将待排序的元素序列一分为二分，得到两个长度基本相等的子序列； 然后对两个子序列分别排序，如果子序列较长，还可继续细分，直到子序列的长度不超过1为止； 当分解所得的子序列已排列有序，可以将两个有序子序列，合并成一个有序子序列 ---合并排序 2019/4/5

template <class T> 【程序5－10】两路合并排序 template <class T> void SortableList<T>::MergeSort(int left,int right) { if (left<right) { int mid = (left+right)/2; MergeSort(left,mid); MergeSort(mid+1,right); Merge(left,mid,right); } 2019/4/5

template <class T> void SortableList<T>::MergeSort() { MergeSort(0,n-1); } 2019/4/5

2019/4/5

性能分析 合并排序递归算法的时间复杂度为O(n log n)。 2019/4/5

5.4.2 快速排序 快速排序采用一种特殊的分划操作对排序问题进行分解，其分解方法是： 5.4.2  快速排序 快速排序采用一种特殊的分划操作对排序问题进行分解，其分解方法是： 在待排序的序列(K0,K1,…,Kn-1)中选择一个元素作为分划元素，也称为主元（pivot）。不妨假定选择K为主元。经过一趟特殊的分划处理将原序列中的元素重新排列，使得以主元为轴心，将序列分成左右两个子序列。主元左测子序列中所有元素都不大于主元，主元右测子序列中所有元素都大于主元。 2019/4/5

分划操作 2019/4/5

template <class T> 【程序5－11】 分划函数 template <class T> int SortableList<T>::Partition(int left, int right) {//前置条件：leftright int i=left, j=right+1; //初始主元放在最左边 do{ do i++; while (l[i]<=l[left]); do j--; while (l[j]>l[left]); if (i<j) Swap(i,j); //交换 }while (i<j); Swap(left,j); //主元作为分界线 return j; //返回主元位置 } 2019/4/5

快速排序算法 2019/4/5

template <class T> void SortableList<T>::QuickSort() { 【程序5－12】快速排序 template <class T> void SortableList<T>::QuickSort() { QuickSort(0,n-1); } void SortableList<T>::QuickSort(int left,int right) if(left<right){ int j=Partition(left,right); QuickSort(left,j-1); QuickSort(j+1,right); 2019/4/5

时间分析 存在的最坏情况 存在的最好情况 最坏情况时间 W(n) W(n-1)+n+1  W(n-2)+(n+1)+n = O(n2) 2019/4/5

平均情况时间 2019/4/5

2019/4/5

5.4.3 排序算法的时间下界 定理 5－7 任何一个通过关键字值比较对n个元素进行排序的算法，在最坏情况下，至少需作（n/4）log n次比较。 2019/4/5

合并排序与快速排序比较 1. 基本思想 2. 划分与组合方法的区别 3. 时间复杂度 2019/4/5

5.5 选择问题 2019/4/5

问题 选择问题（select problem）是指在n个元素的集合中，选出某个元素值大小在集合中处于第k位的元素，即所谓的求第k小元素问题(kth-smallest)。 2019/4/5

5.5.1  分治法求解 设原表长度为n，假定经过一趟分划，分成两个左右子表，其中左子表是主元及其左边元素的子表，设其长度为p，右子表是主元右边元素的子表。那么，若k=p，则主元就是第k小元素；否则若k<p ，第k小元素必定在左子表中，需求解的子问题成为在左子表中求第k小元素；若k>p，则第k小元素必定在右子表中，需求解的子问题成为在右子表中求第k-p小元素。 2019/4/5

5.5.2  随机选择主元 随机选主元算法 假定表中元素各不相同，并且随机选择主元，即在下标区间[left,right]中随机选择一个下标r，以该下标处的元素为主元。 2019/4/5

【程序5－13】Select函数 ，元素集合为l template <class T> ResultCode SortableList<T>::Select1(T& x,int k) { //在l中找到第k大元素，通过x返回 if(n<=0||k>n||k<=0) return OutOfBounds; int left=0, right=n; l[n] = INFTY; do { int j=rand()% (right-left+1)+left; //确定主元 Swap(left,j); j=Partition(left, right); //划分 if (k==j+1) {x=l[j];return Success;} else if (k<j+1) right=j; else left=j+1; } while (true); } 2019/4/5

程序5－13的Select算法的平均时间A(n)=O(n)。 算法的最坏情况时间复杂度O(n2) ，？。 定理5－8 程序5－13的Select算法的平均时间A(n)=O(n)。 算法的最坏情况时间复杂度O(n2) ，？。 2019/4/5

5.5.3  线性时间选择算法 改进的选择算法采用二次取中法(median of medians rule)确定主元 2019/4/5

2019/4/5

ResultCode SortableList<T>::Select(T& x,int k) { 【程序5－14】 线性时间选择算法 ResultCode SortableList<T>::Select(T& x,int k) { if(n<=0||k>n||k<=0) return OutOfBounds; int j=Select(k,0,n-1,5); x=l[j];return Success; } 2019/4/5

} template <class T> int SortableList<T>::Select(int k, int left, int right, int r) { //对[left…right]范围内的元素分组，每组r个元素采用二次取中法，确定主元 int n=right-left+1; if (n<=r){ InsertSort(left,right); //直接排序 return left+k-1; } 2019/4/5

for (int i=1;i<=n/r;i++){ InsertSort(left+(i-1)*r,left+i*r-1); //对每组元素直接排序 Swap(left+i-1, left+(i-1)*r+Ceil(r,2)-1); } int j=Select(Ceil(n/r,2),left,left+(n/r)-1,r ); //定主元 Swap(left,j); j =Partition(left,right); //划分 if (k==j-left+1) return j; else if (k<j-left+1) return Select(k,left,j-1,r); else return Select(k-(j-left+1),j+1,right,r); 2019/4/5

5.5.4 时间分析 以二次取中的中间值mm为主元，经过一趟分划，左、右两个子表的大小均至多为： nn/r/2 r/2 设T(n)为当表长为n时执行程序5－14所需的时间。T(n)由三部分时间组成： T(n)T(n/5)+T(3n/4)+cn 用归纳法容易证明，T(n)20cn，n1是线性时间的。 2019/4/5

5.5.5 允许重复元素的选择算法 由于允许包含相同元素，左子表中除了小于mm的元素外，还包含与mm相同值的元素。因此，左子表的大小至多可达 5.5.5 允许重复元素的选择算法 由于允许包含相同元素，左子表中除了小于mm的元素外，还包含与mm相同值的元素。因此，左子表的大小至多可达 nn/r/2 r/2+1/2 n/r/2 r/2 = n-1/2 n/r/2 r/2 容易用归纳法证明对于所有n90， T(n)T(n/9)+T(7n/8)+cn72cn，n90 2019/4/5

5.6 斯特拉森矩阵乘法 2019/4/5

问题 矩阵相乘C = A x B 2019/4/5

5.6.1 分治法求解 T(n)=(n3) C11＝A11B11+A12B21 C12＝A11B12+A12B22 C21＝A21B11+A22B21 C22＝A21B12+A22B22 2019/4/5

5.6.2  斯特拉森分治法 P=(A11+A22)(B11+B22) Q=(A21+A22)B11 R=A11(B12-B22) S=A21(B21-B11) T=(A11+A12)B22 U=(A21-A11)(B11+B12) V=(A12-A22)(B21+B22) 2019/4/5

C11=P+S-T+V C12=R+T C21=Q+S C22=P+R-Q+U T(n)= (nlog 7)(n2. 81) 2019/4/5

练习2 设计算法解决大数相乘问题（长为n位的两个2进制数相乘）使其算法复杂度低于n2。 2019/4/5