Intro to Alg

Size: px

Start display at page:

Download "Intro to Alg"

丁奚
5 years ago
Views:

1 算法基础 Foudatio of Algorithms 主讲人徐云 Fall 2018, USTC

2 第 1 章 ( 补充 ) 递归与分治法 1.1 递归设计技术 1.2 二分查找 1.3 大整数乘法 1.4 Strasse 矩阵乘法 1.5 导线和开关

3 1.1 递归设计技术递归的概念和种类递归方法的三种应用一个简单示例 :! 递归算法的非递归实现递归算法设计举例 2018/9/27 算法基础 3

4 递归的定义递归的概念和种类若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的 ; 若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程递归有两种直接递归 : 自己调用自己间接递归 :A 调用 B,B 调用 A 2018/9/27 算法基础 4

5 递归方法的三种应用以下三个方面常用到递归方法 1 递归定义如, 自然数定义 : - 1 是自然数 ; - 一个自然数加 1( 后继 ) 仍是自然数 ; 注 : 1 是自然数是递归的临界条件 2 递归的数据结构如, 单链表节点是递归扩展的 3 问题的递归解法如, 汉诺塔问题的直观解法 2018/9/27 算法基础 5

6 一个简单示例 :! 阶乘的定义 : 1! *( 1)! 0 0 以求 3! 为例的计算过程 Fact(3) Fact(3) 逐层调用 3*Fact(2) Fact(2) 2*Fact(1) Fact(1) 1 Fact(2) =2 =6 逐层返回 2018/9/27 算法基础 6

7 递归算法的非递归实现示例 :! 的递归和非递归算法 Fact1() // 递归程序 { if =0 retur 1; { p=1; Fact2(it ) // 非递归程序 else retur *fact1(-1); for i 1 to do p p*i; } retur p; Remark: } (1) 递归算法易设计和分析, 但执行效率较低, 常要转化为非递归程序 ; (2) 递归算法的非递归实现通常有三种实现方法 : 1 利用栈消除递归 3 末尾递归消除法 2 利用迭代法消除递归 2018/9/27 算法基础 7

8 递归算法的非递归实现思考题 : Fiboacci 数递归和非递归算法 Fiboacci() { // 递归算法 } if =0 or =1 the else F retur ; F F 2 2 retur Fiboacci(-1) + Fiboacci(-2) ; Fiboacci() { // 非递归算法 if =0 or =1 the } retur ; s1 = 0; s2 = 1; for i 2 to do { sum s1 + s2; s1 s2; s2 sum; } retur sum; 2018/9/27 算法基础 8

9 递归算法设计举例 : 汉诺塔 (1) 汉诺塔 ( Haoi Tower) 问题 : 这是一个流传很久的游戏 1. 有三根杆子 A,B,C A 杆上有只碟子 2. 每次移动一块碟子, 小的只能叠在大的上面 3. 把所有碟子从 A 杆经 C 杆全部移到 B 杆上. Peg #1 Peg #2 Peg #3 2018/9/27 算法基础 9

10 递归算法设计举例 : 汉诺塔 (2) 递归求解 : 1. 若只有一只碟子, 直接将它从 A 杆移到 B 杆 ; 2. 把 -1 只碟子从 A 杆经 B 杆移动到 C 杆, 将 A 杆上第只碟子移到 B 杆 ; 然后再将 -1 只碟子从 C 杆经 A 杆移到 B 杆 2018/9/27 算法基础 10

11 递归算法设计举例 : 汉诺塔 (3) 递归算法 Haoi(, A, B, C) { // 将从小到大的个圆盘从 A 移到 B } if >0 the { Haoi(-1, A, C, B); // 将从小到大的 -1 个圆盘从 A 移到 C } Move(, A, B); 算法分析 // 将第大的圆盘从 A 移到 B Haoi(-1, C, B, A); // 将从小到大的 -1 个圆盘从 C 移到 B 正确性 : 用归纳法证明 ; 时间复杂性 :T()=1+2T(-1) O(2 ) 算法的最优性 : 为最优的 2018/9/27 算法基础 11

12 递归算法设计举例 : 再论 Fib 数 (1) 基于 Fiboacci 数递归定义的算法 :T()=Ω((3/2) ) 改进的算法 : 利用公式 F - 算法 : F / 2 F / 21 2 F 2 / 2 F / 2 F / 2 Fiboacci(it ) a Fiboacci((+1)/2); { if =0 or =1 the b Fiboacci((+1)/2-1); retur ; if mod 2 = 0 the else { retur a*(a+2*b); else retur a*a+b*b; } } 且为奇数 2且为偶数 2018/9/27 算法基础 12

13 递归算法设计举例 : 再论 Fib 数 (2) - 时间分析 : O(1) T( ) 2T ( / 2) O(1) 应用主方法 : f ( ) 1 由 case 1: log 2 T( ) ( ) 2 ( 这里 =1/ 2) 2018/9/27 算法基础 13

14 递归算法设计举例 : 生成全排列 (1) 问题描述 : 编写一个算法, 就地生成字符数组 S[1..] 的所有排列, 要求算法终止时 S[1..] 保持初始状态就地生成表示不使用 S 以外的数组问题分析 - 分解 : 将原问题分解为个子问题, 子问题 1: 生成 -1 个元素 s[1],,s[-1] 的全排列后接 s[]; 子问题 2: 生成 -1 个元素 s[1],,s[-2],s[] 的全排列后接 s[-1]; 子问题 : 生成 -1 个元素 s[2],,s[] 的全排列后接 s[1]; - 递归求解 : 子问题与原问题的性质相同, 只不过规模为 -1 设原问题的求解算法为 permute(s,), 则子问题就是递归调用 permute(s,-1) 临界条件 : 一个元素的排列就是该元素本身 2018/9/27 算法基础 14

15 递归算法设计举例 : 生成全排列 (2) 算法 Permute( s[], ) { // 个元素 s[1..], 输出所有的排列 if =1 the prit(s); // 输出 s 的一个排列 else { Permute(s, -1); // 第一个子问题求解, 不需要交换 s[] for i -1 dowto 1 do { swap(s[i], s[]); // 交换 s[i], s[] Permute(s, -1); swap(s[i], s[]); // 交换 s[i], s[], 使 s 恢复原状 } } } 2018/9/27 算法基础 15

16 2018/9/27 算法基础 16 递归算法设计举例 : 生成全排列 (3) 时间分析注 : 该算法是最优的!) ( ) ( 1 1 ) ( 1) ( (1) ) ( O T O T O T =

17 递归算法设计举例 : 集合划分 (1) 问题描述 : 设有个元素的集合 s={a 1,a 2,,a }, 要求将 s 划分为 k 个子集 s 1,s 2,,s k, 且满足 : 1s i φ; 2s i s j =φ i j; 3s=s 1 s 2 s k 求 s 的 k 划分数问题分析 - 例如 :s={1,2,3,4},k=3, 共有 6 种不同的划分, 即划分数为 6, 这些划分为 {1,2} {3} {4}; {1,4} {2} {3}; {2,3} {1} {4}; {3,4} {1} {2}; {1,3} {2} {4}; {2,4} {1} {3}; 2018/9/27 算法基础 17

18 递归算法设计举例 : 集合划分 (2) 问题分析 (cot.) - 递归关系的推导设个元素 a 1,a 2,,a 放入 k 个集合的划分数为 s(,k), 考虑 a 的二种情形 : Case 1: 设 {a } 恰为 k 个子集中的一个, 此时划分数为 s(-1,k-1) Case 2: {a } 不是 k 个子集中的一个, 即 a 与其它元素构成一个子集这时可以先将 {a 1,a 2,,a -1 } 划分成 k 个子集, 共有 s(-1,k) 种划分, 再将 a 加入到 k 个子集中的某个子集中去, 共有 k 种方式由乘法原理知 : 划分数有 k*s(-1,k) => s(,k)=s(-1,k-1)+k*s(-1,k) >k 且 k>1 2018/9/27 算法基础 18

19 2018/9/27 算法基础 19 递归算法设计举例 : 集合划分 (3) 问题分析 (cot.) - 递归关系的推导下面确定 s(,k) 的边界条件 : (1)s(,0)=0, 即个元素不放入任何一个集合中去 ; (2)s(,1)=1,s(,)=1 k k k k k k k s k k s k s 或或且 ) 1, ( 1) 1, ( ), (

20 递归算法设计举例 : 集合划分 (4) 算法 S(, k) { if k=0 or <k the retur 0; else if k=1 or =k the retur 1; else retur s(-1,k-1)+k*s(-1,k); } 时间分析? 2018/9/27 算法基础 20

21 第 1 章 ( 补充 ) 递归与分治法 1.1 递归设计技术 1.2 二分查找 1.3 大整数乘法 1.4 Strasse 矩阵乘法 1.5 导线和开关

22 1.2 二分查找基本思想递归算法非递归算法 2018/9/27 算法基础 22

23 基本思想和非递归算法基本思想将有序序列 ( 升序 ) 等分为几乎相等的两部分, 待查关键字与划分元比较如果小于划分元, 则递归处理左半部分 ; 否则, 递归处理右半部分非递归算法 BiarySearch1(L[ ],, x) // 找到 x 返回下标值, 找不到返回 -1 { left 1, right ; flag 0; //flag 为标志变量 while (left right ad flag=0) do { mid (left+right)/2; if x=l[mid] the flag 1; else if x<l[mid] the right mid-1; else left mid+1; } if flag=1 the retur mid; else retur -1; } 2018/9/27 算法基础 23

24 递归算法递归算法 BiarySearch2(L[ ], x, i, j) { // 在有序表 L[i..j] 中查找 x if i>j the retur -1; if i=j the if x=l[i] the retur i; else retur -1; else { mid (i+j)/2; } } 时间分析 O(1) T ( ) T ( / 2) O(1) T ( ) O(log ) if x=l[mid] the retur mid; else if x<l[mid] the retur BiarySearch2(L, x, i, mid-1); else retur BiarySearch2(L, x, mid+1, j); /9/27 算法基础 24

25 第 1 章 ( 补充 ) 递归与分治法 1.1 递归设计技术 1.2 二分查找 1.3 大整数乘法 1.4 Strasse 矩阵乘法 1.5 导线和开关

26 1.3 大整数乘法问题描述普通递归乘法分析改进的分治乘法 2018/9/27 算法基础 26

27 问题描述处理很大的整数时, 它无法在计算机硬件能直接表示的范围内进行处理若用浮点数来表示它, 则只能近似地表示它的大小, 计算结果中的有效数字也受到限制若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字, 就必须用软件的方法来实现大整数的算术运算 2018/9/27 算法基础 27

28 普通递归乘法分析设 X, Y 是位二进制整数, 分段表示如下 : 即 X=A2 /2 +B, Y=C2 /2 +D 则 XY=(A2 /2 +B)(C2 /2 +D)=AC2 +(AD+BC) 2 /2 +BD 计算成本 :4 次 /2 位乘法,3 次不超过位加法,2 次移位, 所有加法和移位共计 O() 次运算我们有 => T()=O( 2 ) 2018/9/27 算法基础 28

29 改进的分治乘法 (1) 1962 年苏联数学家 Karatsuba 和 Ofma 提出由 X=A2 /2 +B, Y=C2 /2 +D 则 XY=(A2 /2 +B)(C2 /2 +D)=AC2 +(AD+BC) 2 /2 +BD = AC2 +((A-B)(D-C)+AC+BD)2 /2 +BD 计算成本 :3 次 /2 位乘法,6 次不超过位加减法,2 次移位, 所有加法和移位共计 O() 次运算由此可得, => T()=O( log3 )=O( 1.59 ) 注 : 如果将一个大整数分成 3 段或 4 段做乘法, 计算复杂性会发生什么变化呢? 是否优于分成 2 段的乘法? 这个问题请大家自己考虑 2018/9/27 算法基础 29

30 改进的分治乘法 (2) 改进的分治算法举例已知 X=2368,y=3925, 求 XY 解 : 取基 d=10, A=23, B=68, C=39, D=25, 则 1 AC=23 39=897 2 BD=68 25= (A-B)(D-C)+AC+BD =(23-68)(25-39) = =3227 XY= = 共做 12 次位乘, 而普通乘法要做 16 次位乘注 : 大整数乘法在数据加密领域中有广泛应用, 值的位数通常在 200 位以上 2018/9/27 算法基础 30

31 第 1 章 ( 补充 ) 递归与分治法 1.1 递归设计技术 1.2 二分查找 1.3 大整数乘法 1.4 Strasse 矩阵乘法 1.5 导线和开关

32 1.4 Strasse 矩阵乘法普通矩阵乘法 Strasse 矩阵乘法 2018/9/27 算法基础 32

33 普通矩阵乘法设阶矩阵 A 和 B, 计算 C=A B c ij k 1 a ik b kj i, j 1,2,, 求 C=AB 即对 2 个元素 c ij 进行计算, 故要作 3 次乘法相当长时间内没有人怀疑过是否可以用少于 3 次乘法来完成 2018/9/27 算法基础 33

34 2018/9/27 算法基础 34 Strasse 矩阵乘法 (1) 以 =2 为例的普通矩阵乘法设则有共需 8 次乘法 , b b b b B a a a a A b b b b a a a a AB C b a b a b a b a b a b a b a b a c c c c

35 Strasse 矩阵乘法 (2) Strasse 的分治算法 (1969) - 将 C=A B 写为 2 2 的分块矩阵 : C C Strasse 提出的算法如下 : C C 令 P=(A 11 +A 22 )(B 11 +B 22 ), Q=(A 21 +A 22 )B 11 R=A 11 (B 12 -B 22 ), S=A 22 (B 21 -B 11 ) T=(A 11 +A 12 )B 22, U=(A 21 -A 11 )(B 11 +B 12 ) V=(A 12 -A 22 )(B 21 +B 22 ) 则 C 11 =P+S-T+V, C 12 =R+T C 21 =Q+S, A = A 乘法次数从 8 次减为 7 次 A A B B B B C 22 =P+R-Q+U /9/27 算法基础 35

36 - 时间分析 : Strasse 矩阵乘法 (3) 用了 7 次对于 /2 阶矩阵乘积的递归调用和 18 次 /2 阶矩阵的加减运算由此可知, 该算法的所需的计算时间 T() 满足如下的递归方程 : T O(1) ) 7T ( / 2) O( ( 2 => T()=O( log7 ) O( 2.81 ) - Remark:. 有人提出了计算 2 2 阶矩阵乘法的 36 种不同方法, 都只要做 7 次乘法 ;. Hopcroft 和 Kerr(1971) 已经证明,7 次乘法是必要的 ;. 是否研究 3 3 或 5 5 矩阵的更好算法?. 目前最好的计算时间上界是 O( ), 而最好下界仍是 Ω( 2 ) ) /9/27 算法基础 36

37 第 1 章 ( 补充 ) 递归与分治法 1.1 递归设计技术 1.2 二分查找 1.3 大整数乘法 1.4 Strasse 矩阵乘法 1.5 导线和开关

38 1.5 导线和开关问题描述穷举检测法分治检测法 2018/9/27 算法基础 38

39 问题描述如图所示, 具有 3 根导线的电缆把 A 区和 B 区连接起来在 A 区 3 根导线标以 1,2,3; 在 B 区导线 1 和 3 被连到开关 3, 导线 2 连到开关 1 一般地, 电缆含 m(1 m 90) 根导线, 在 A 区标以 1,2,...,m 在 B 区有 m 个开关, 标为 1,2,..,m 每一根导线都被严格地连到这些开关中的某一个上 ; 每一个开关上可以连有 0 根或多根导线算法应作出哪些测量来确定导线和开关的连接, 使测量数最少, 这些测量是探头的移动和开关的开闭数 2018/9/27 算法基础 39

40 算法描述穷举检测法将探头 p 移到导线 i, i=1,2,,m; 顺序闭合开关 j, j=1,2,,m; 操作数分析如果灯 L 亮, 则导线 i 与开关 j 相连 ; 否则, 导线 i 与开关 j 不相连 ; 将开关 j 打开 ; 探头移动 m 次, 每次开关操作 2m 次, T(m)=O(m 2 ) 操作举例 (3 根导线 3 个开关 ) 探头移动 3 次, 开关操作 (6+2+6)=14 次 2018/9/27 算法基础 40

41 算法描述分治检测法 (1) 第 1 轮操作 :// 确定每根导线属于哪半区上半区开关合上, 下半区开关断开, 探头遍历 ; 第 2 轮操作 :// 确定每根导线属于哪半半区对每半区再分 : 上半半区开关合上, 下半半区开关断开, 探头遍历 ; 第 log m1轮操作 :// 确定每根导线属于哪个开关每个开关合上, 探头遍历 ; 操作数分析每轮开关开闭 2m 次, T(m)=O(mlogm) 2018/9/27 算法基础 41

42 分治检测法 (2) 操作举例 (3 根导线 3 个开关 ) 探头移动次数开关操作次数合计第 1 轮 : 3 2 第 2 轮 : 2 2 小计 : 注 : 穷举法 : 思考题写出分治检测法的形式化算法 2018/9/27 算法基础 42

43 Ed of SCh1

Microsoft PowerPoint - schap1 [兼容模式]

Microsoft PowerPoint - schap1 [兼容模式] 算法设计与分析 Desig ad Aalysis of Algorithms 主讲人徐云 Fall 2018, USTC 第 1 章 ( 补充 ) 递归与分治法 1.1 递归设计技术 1.2 二分查找 1.3 大整数乘法 1.4 Strasse 矩阵乘法 1.5 导线和开关 1.1 递归设计技术递归的概念和种类递归方法的三种应用一个简单示例 :! 递归算法的非递归实现递归算法设计举例 2018/9/25