Microsoft PowerPoint - Chap02.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - Chap02.pptx"

管蒙
4 years ago
Views:

1 算法分析与设计 Analysis and Design of Algorithm Lesson 05

2 要点回顾递归算法概念 ( 阶乘 Fibonacci 数列双递归 ) 例子 ( 整数划分问题 Hanoi 塔问题 ) Hanoi 塔算法运行轨迹分析时间复杂度递推方程 ( 迭代法求解 ) 递归的优缺点 39

3 分治策略

4 分治法 (Divide-and-Conquer) 基本思想 : 将一个规模为 n 的问题分解为 k 个规模较小的子问题, 这些子问题互相独立且与原问题相同递归解这些子问题, 再将子问题合并得到原问题的解子问题 1

5 分治法的适用条件分治法所能解决的问题一般具有以下几个特征 : 该问题的规模缩小到一定的程度就可以容易地解决 ; 因为问题的计算复杂性一般是随着问题规模的增加而增加, 因此大部分问题满足这个特征 2

6 分治法的适用条件分治法所能解决的问题一般具有以下几个特征 : 该问题的规模缩小到一定的程度就可以容易地解决 ; 该问题可以分解为若干个规模较小的相同问题, 即该问题具有最优子结构性质这条特征是应用分治法的前提, 它也是大多数问题可以满足的, 此特征反映了递归思想的应用 3

7 分治法的适用条件分治法所能解决的问题一般具有以下几个特征 : 该问题的规模缩小到一定的程度就可以容易地解决 ; 该问题可以分解为若干个规模较小的相同问题, 即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解 ; 能否利用分治法完全取决于问题是否具有这条特征, 如果具备了前两条特征, 而不具备第三条特征, 则可以考虑贪心算法或动态规划

8 分治法的适用条件分治法所能解决的问题一般具有以下几个特征 : 该问题的规模缩小到一定的程度就可以容易地解决 ; 该问题可以分解为若干个规模较小的相同问题, 即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解 ; 该问题所分解出的各个子问题是相互独立的, 即子问题之间不包含公共的子问题该特征涉及到分治法效率, 如果各子问题不独立, 则分治法要做许多不必要的工作, 重复地解公共子问题, 此时虽也可用分治法, 但一般用动态规划较好 5

9 分治法的基本步骤伪代码 : divide-and-conquer(p){ if ( P <= n 0 ) adhoc(p); //(1) 解决小规模的问题 divide P into smaller sub instances P 1,P 2,...,P k ; //(2) 分解问题 for (i=1,i<=k,i++) y i =divide-and-conquer(p i ); //(3) 递归地解各子问题 return merge(y 1,...,y k );//() 将各子问题的解合并为原问题的解 } 其中, P 是问题 P 的规模,n 0 为一阈值, 表示当问题 P 的规模不超过 n 0 时, 问题已容易解决, 不必再继续分解 adhoc(p) 是分治的基本子算法, 用于直接解小规模的问题 P merge(y 1,y 2,...,y k ) 是分治算法中的合并子算法 6

10 分治法的问题将问题分为多少个子问题? 子问题的规模是否相同 / 怎样才恰当? 研究者从大量实践中发现, 在用分治法设计算法时, 最好使子问题的规模大致相同即, 将一个问题分成大小相等的 k 个子问题的处理方法是行之有效的这种使子问题规模大致相等的做法是出自一种叫做平衡 (balancing) 子问题的思想, 它几乎总是比子问题规模不等的做法要好 7

11 分治法的计算效率采用分治法解规模为 n 的问题的效率分析, 假定 : 分成 k 个规模为 n/m 的子问题去解解规模为 1 的问题耗费 1 个单位时间分解为 k 个子问题和将 k 个子问题的解合并需用 f(n) 个单位时间用 T(n) 表示该分治法解规模为 P =n 的问题所需的计算时间 : T ( n) 迭代法求方程解 : (1) kt( n / m) f ( n) n n 1 1 log m n1 log m k j j Tn ( ) n k fn ( / m) j0 8

12 从游戏开始 9

13 二分搜索技术问题 : 给定已按升序排好序的 n 个元素 a[0:n-1], 现要在这 n 个元素中找出一特定元素 x 分析 : 1. 该问题的规模缩小到一定的程度就可以容易地解决 ; 如果 n=1 即只有一个元素, 则只要比较这个元素和 x 就可以确定 x 是否在表中因此这个问题满足分治法的第一个适用条件 50

14 二分搜索技术问题 : 给定已按升序排好序的 n 个元素 a[0:n-1], 现要在这 n 个元素中找出一特定元素 x 分析 : 1. 该问题的规模缩小到一定的程度就可以容易地解决 ; 2. 该问题可以分解为若干个规模较小的相同问题 ; 3. 分解出的子问题的解可以合并为原问题的解 ; 比较 x 和中间元素 a[mid], 若 x=a[mid], 则 x 在 L 中的位置就是 mid; 如果 x<a[mid], 由于 a 是递增排序的, 因此假如 x 在 a 中的话,x 必然排在 a[mid] 的前面, 所以只要在 a[mid] 的前面查找 x 即可 ; 如果 x>a[i], 同理只要在 a[mid] 的后面查找 x 即可无论是在前面还是后面查找 x, 其方法都和在 a 中查找 x 一样, 只不过是查找的规模缩小了这就说明了此问题满足分治法的第二三个适用条件 51

15 二分搜索技术问题 : 给定已按升序排好序的 n 个元素 a[0:n-1], 现要在这 n 个元素中找出一特定元素 x 分析 : 1. 该问题的规模缩小到一定的程度就可以容易地解决 ; 2. 该问题可以分解为若干个规模较小的相同问题 ; 3. 分解出的子问题的解可以合并为原问题的解 ;. 分解出的各个子问题是相互独立的很显然此问题分解出的子问题相互独立, 即在 a[i] 的前面或后面查找 x 是独立的子问题, 因此满足分治法的第四个适用条件 52

16 二分搜索算法据此容易设计出二分搜索算法 : template<class Type> int BinarySearch(Type a[], const Type& x, int l, int r){ } while (r >= l){ int m = (l+r)/2; if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; } return -1; 算法复杂度分析 : 每执行一次算法中的 while 循环, 待搜索数组的大小减少一半因此, 在最坏情况下, while 循环被执行了 (logn) 次循环体内运算需要 (1) 时间, 因此整个算法在最坏情况下的计算时间复杂性为 (logn) 53

17 二分搜索算法 (cont.) 二分搜索算法易于理解编写正确的二分搜索算法不易,90% 人在 2 个小时内不能写出完全正确的二分算法第一个二分搜索算法在 196 年提出, 但是第一个完全正确的二分搜索算法却直到 1962 年才出现 5

18 大整数的乘法在复杂性计算时, 都将加法和乘法运算当作基本运算处理, 即加乘法时间为常数但上述假定仅在参加运算整数能在计算机表示范围内直接处理时才合理那么我们处理很大的整数时, 怎么办? 要精确地表示大整数, 并在计算结果中精确到所有位数, 就必须用软件方法实现 55

19 大整数的乘法 (cont.) 问题 : 请设计一个有效的算法, 可以进行两个 n 位大整数的乘法运算小学的方法 :(n 2 ) 效率太低了!!! 56

20 大整数的乘法 (cont.) 问题 : 请设计一个有效的算法, 可以进行两个 n 位大整数的乘法运算小学的方法 :(n 2 ) 分治法 : 假设 :X 和 Y 都是 n 位二进制整数效率太低了!!! n/2 位 n/2 位 X= a b n/2 位 n/2 位 Y= c d X= a 2 n/2 + b Y= c 2 n/2 + d XY = ac 2 n + (ad+bc) 2 n/2 + bd 57

21 复杂度分析则计算 X,Y, 需次 n/2 位整数乘法 (ac,ad,bc 和 bd) 需 3 次小于 2n 位的整数加需 2 次移位 (2 n, 2 n/2 ) 共需 (n) (1) T ( n) T ( n / 2) ( n) n 1 n 1 直接用之前的迭代法解有点点复杂! 58

22 换元迭代法将对 n 的递推式换成对其他变元 k 的递推式对 k 直接迭代将解 ( 关于 k 的函数 ) 转换成关于 n 的函数举例 : 解如下递推方程 T(n)=2T(n/2)+n-1 T(1)=0 换元 : 令 n=2 k, 则递推方程变换为 T(2 k )=2T(2 k /2)+2 k -1 =2T(2 k-1 )+2 k -1 T(0)=0 59

23 换元迭代法 T(2 k )=2T(2 k-1 )+2 k -1 T(0)=0 迭代求解 : T(n)=T(2 k )=2T(2 k-1 )+2 k -1 =2[2T(2 k-2 )+2 k-1-1]+2 k -1 =2 2 T(2 k-2 )+2 k -2+2 k -1 = =2 k T(1)+k2 k -(2 k-1 +2 k ) = k2 k -2 k +1 =nlogn-n+1 最后, 需用数学归纳法证明正确性! 60

24 61 复杂度分析则计算 X,Y, 需次 n/2 位整数乘法 (ac,ad,bc 和 bd) 需 3 次小于 2n 位的整数加需 2 次移位 (2 n, 2 n/2 ) 共需 (n) 1 1 ) ( 2) / ( (1) ) ( n n n n T n T T T T T 为了简化, 设 n 为 2 的幂换元迭代法 n=2 x

25 62 复杂度分析公式法求解该算法复杂度 : 1 1 ) ( 2) / ( (1) ) ( n n n n T n T T T x x 没有改进!!! T(n)=(n 2 ) T(n)=(n 2 )

26 大整数的乘法 (cont.) 为了降低时间复杂度, 必须减少乘法的次数!!! 1. XY = ac 2 n + ((a-b)(d-c)+ac+bd) 2 n/2 + bd 2. XY = ac 2 n + ((a+b)(d+c)-ac-bd) 2 n/2 + bd 对于 1 式 : 需 3 次 n/2 位整数乘法 ((a-b)(d-c),ac,bd) 需 6 次加减需 2 次移位 63

27 大整数的乘法 (cont.) 复杂度分析 : T ( n) 3T ( n (1) / 2) ( n) n n 1 1 T(n)=(n log3 ) =(n 1.59 ) 改进了!!! 细节问题 : 两个 XY 的复杂度都是 (n log3 ), 但考虑到 a+b, c+d 可能得到 n+1 位的结果, 使问题的规模变大, 故不选择第 2 种方案 6

28 大整数的乘法 (cont.) 还有没有更快的方法? T(n)=(n log3 ) =(n 1.59 ) 如果将大整数分成更多段, 用更复杂的方式把它们组合起来, 将有可能得到更优的算法最终的, 这个思想导致了快速傅利叶变换 (Fast Fourier Transform) 的产生该方法也可以看作是一个复杂的分治算法 65

29 大整数的乘法 (cont.) 是否能找到线性时间算法? 目前为止还没有结果 66

30 递归树法验证换元迭代法递归树的概念递归树是迭代计算的模型 ( 迭代的图形表示 ) 递归树的生成过程与迭代过程一致树上所有项恰好是迭代之后产生和式中的项对递归树上的项求和就是迭代后方程的解 67

31 递归树法验证换元迭代法迭代在递归树中的表示如果递归树上某节点标记为 W(m) W(m)= W(m 1 ) + + W(m k ) + f(m) + + g(m), m 1,.., m k <m 其中 W(m 1 ),,W(m k ) 称为函数项 W(m) 节点总值相等 f(m) + + g(m) 递归求解划分后的子问题的开销归约到子问题及合并解的开销 W(m 1 ) W(m 2 )W(m 3 ) W(m k ) 每个叶节点是一个函数项 68

32 例子 : 画出 T(n)=2T(n/2)+n 递归树 T(1)=1 69

33 T(n)=2T(n/2)+n T(1)=1 70

第2章递归与分治策略

第2章递归与分治策略 : 1. 2. 3. Strassen 4. 5. 6. 7. 8. 9... 2 T(n) = n T(n/2) T(n/2) T(n/2) T(n/2) 3 T(n) = n n/2 n/2 n/2 n/2 T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4