设计 郑宗汉郑晓明 第4章+递归和分治_44359.ppt

for (i=0; in/5; i++) //每组中值存于p mid(A, i, p); m = select(p, i, ?i/2?); //递归调用 i = j = s = 0; for (t=0; tn; t++) { //根据m划分数组 if (A[t]m) p[i++]=A[t]; else if (A[t]= =m) q[j++]=A[t]; else r[s++]=A[t]; if (ik) return select(p, i, k); //在p中找 else if (i+j=k) return m; //m为第k小 else return select(r, s, k-i-j); //在r中 } 3. 选择算法的分析 令n0=38, 对所有的n?n0, 都有 0.7n+1.2 ? ?3n/4? 递归方程展开后得: 空间复杂性: 算法所需要的工作空间为O(n)。 第4章 递归和分治4.1 基于归纳的递归算法 例4.1 计算阶乘函数 算法4.1 计算阶乘函数 输入: n 输出: n! int factorial(int n) { if (n==0) return 1; else return n?factorial(n-1); } 4.2 分治法 例4.4 最大最小问题? 算法4.6 求最大最小元素的一般算法 输入: n个元素的数组A[] 输出: 最大元素max和最小元素min void max_min(int A[], int max, int min, int n) { int i; max=A[0]; min=A[0]; for (i=1;in;i++) { if (A[i]min) min=A[i]; if (A[i]max) max=A[i]; } }? 元素比较次数是2(n-1) 算法4.7 分治法求解最大最小元素 输入: 整数数组A[], 下标界low和high 输出: 最大元素max和最小元素min void maxmin(int A[], int emax, int emin, int low, int high) { int mid, x1, y1, x2, y2; if ((high-low = 1)) { if (A[high]A[low]) {emax=A[high]; emin=A[low];} else {emax=A[low]; emin=A[high];}} else {mid = (low+high)/2; maxmin(A,x1,y1, low, mid); maxmin(A,x2,y2,mid+1,high); emax = max(x1, x2); emin = min(y1, y2);} } 分治法求最大最小元素的工作过程: 时间复杂性分析: 假定n=2k, 令C(n)表示对n元素数组执行的比较次数, 递归方程如下: 令C(n) = C(2k) = h(k), 上面方程改写为: 故 时间复杂度为3n/2-2。 空间复杂度分析: 递归深度为k=logn, 每递归调用一次, 分配常数个工作单元, 故空间复杂度为?(logn)。 4.2.2 分治法的设计原理 1. 基本思想: 把规模为n的问题分解为k个规模较小、互相独立、结构与原问题相同的子问题, 进一步分解每个子问题, 直到某个阀值n0为止。 递归地求解这些子问题, 再把子问题的解合并, 得到原问题的解。 2. 分治法的设计步骤: divide_and_conquer(P(n)) { if (n=n0) return adhoc(P(n)); else {divide into P1,P2,?,Pk; for (i=1; i=k; i++) yi=divide_and_conquer(Pi); return merge(y1,y2,?,yk); } } adhoc: 直接求解规模较小的问题P merge: 把P1,P2,?,Pk的解y1,?,yk合并 分治法可划分为三个步骤: 1. 划分步: 把实例