幻灯片 1

Size: px

Start display at page:

Download "幻灯片 1"

歪又钱
5 years ago
Views:

1 算法分析与设计 Analysis and Design of Algorithm 第 3 次课

2 要点回顾算法复杂度的概念时间复杂度空间复杂度复杂度的渐近性态略去低阶项所留下的主项五个渐近分析记号及其性质 NP 完全性理论问题的复杂度易解难解不可解问题 P NP NPC NP 难问题 1. 渐近上界记号 O 2. 渐近下界记号 3. 紧渐近界记号 4. 非紧上界记号 o 5. 非紧下界记号 2

3 课程信息考核方式平时 ( 点名作业互动 ):30%; 期末 ( 考试 ):70% 作业要求习题类型 : 算法分析题 + 算法实现题截至日期 : 一周之内完成提交形式 : 纸质版和电子版 ( 关于算法实现题, 纸质版需提交运行界面截图, 无需源码 ; 电子版需要截图源码可执行程序 ) 提交方式 : 发邮件至 jjin@seu.edu.cn, 抄送 zyang@seu.edu.cn 邮件格式 : 算法作业 X_ 学号 _ 姓名 (X 为第几次, 如 1,2,3 ) 作业格式 : 推荐用 Latex 编写作业 ( 下载 CTex 并自学 Latex) 答疑方式课程 QQ 群计算机楼 368 室联系助教 ( 周四下午 ) 3

4 课程内容 NP 完全性理论与近似算法算法高级理论随机化算法线性规划与网络流高级算法递归分治动态规划贪心算法回溯与分支限界基础算法算法分析与问题的计算复杂性算法基础理论 4

5 第二章递归与分治策略

6 学习要点理解分治和递归的概念掌握设计有效算法的分治策略通过下面的范例学习分治策略设计技巧二分搜索技术 ; 大整数乘法 ; Strassen 矩阵乘法 ; 棋盘覆盖 ; 合并排序和快速排序 ; 最接近点对问题 ; 循环赛日程表 6

7 分治法的初衷任何一个问题的求解时间都与其规模有关例子 : n 个元素排序 : 当 n=1, 不需计算 ; 当 n=2, 只作一次即可 ; 当 n=3, 三次 or 两次? 显然, 随着 n 的增加, 问题也越难处理 7

8 分治法分治法的设计思想是 : 将一个难以直接解决的大问题, 分割成一些规模较小的相同问题, 以便各个击破, 分而治之如果问题可分割成 k 个子问题, 且这些子问题都可解, 利用这些子问题可解出原问题的解, 此分治法是可行的 8

9 分治法的例子 : 归并排序输入划分划分停止划分合并合并输出

10 分治与递归分治和递归紧密联系由分治法产生的子问题往往是原问题的较少模式, 为递归提供了方便 10

11 递归策略

12 递归定义 : 直接 / 间接调用自身的算法称为递归算法 void mergesort(int[] A,int[] temp, int start,int end){ if (start<end){ int mid = (start+end)/2; // 把数组分解为两个子列 mergesort(a,temp,start,mid); mergesort(a,temp,mid+1,end); // 逐级合并两个子列 Merge(A,temp,start,mid,end); } } 递归第一式给出函数的初值, 非递归定义每个递归须有非递归初始值第二式是用较小自变量的函数值表示较大自变量 12

13 递归前面提到的 Fibonacci 数列 F n 1 1 F, n 0, n 1 n 1 Fn 2, n 1 意大利数学家 Fibonacci

14 Fibonacci 数列 14

15 Fibonacci 数列 Fibonacci 数列也可用非递归方式定义 : F n n1 n1 但是并不是所有的递归表达式都有非递归的形式 15

16 双递归函数一个函数与它的一个变量是由函数自身定义 Ackerman 函数 1. m=0, A(n,0)=n+2 2. m=1, A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2 3. m=2, A n, m A 1,0 2 A 0, m 1 : A n,0 n 2 A n, m AAn 1, m, m,2 AAn 1,2,1 2An 1,2 A n A 1,2 AA0,2,1 A1,1 2 1 m n n, m n, 1 n A 2 n,2 2 A n 16

17 双递归函数 m=3, An,3 2, 其中 2 的层数 n 5. m=4, A(n,4) 的增长速度非常快, 以至于没有适当的数学式子来表示这一函数部分书上减少 Ackerman 函数的变量, 如 : n An n A, 2 2 A 4 =2 ( 其中 2 的层数为 65536) 这个数非常大, 无法用通常的方式来表达它 17

18 整数划分问题前面的几个例子中, 问题本身都具有比较明显的递归关系, 因而容易用递归函数直接求解实际情况下, 许多问题的递归函数并不能快速找出如整数划分问题 18

19 整数划分问题将正整数 n 表示成一系列正整数之和 : n=n 1 +n 2 + +n k, 其中 n 1 n 2 n k 1,k 1 正整数 n 的这种表示称为正整数 n 的划分问题 : 求正整数 n 的不同划分个数例如正整数 6 有如下 11 种不同的划分 : 6; 5+1; 4+2,4+1+1; 3+3,3+2+1, ; 2+2+2, , ;

20 整数划分问题仅仅考虑一个自变量 : 设 p(n) 为正整数 n 的划分数, 但难以找到递归关系考虑两个自变量 : 将最大加数 n 1 不大于 m 的划分个数记作 q(n, m) 20

21 整数划分问题可以建立 q(n, m) 的如下递归关系 (1) q(n,1)=1,n 1; (2) q(n, m)=q(n, n), m n; (3) q(n, n)=1+q(n, n-1); 当最大加数 n 1 不大于 1 时, 任何正整数 n 只有一种划分形式最大加数 n 1 实际上不能大于 n 因此, q(1, m)=1 正整数 n 的划分由 n 1 =n 的划分和 n 1 n-1 的划分组成 (4) q(n, m)=q(n, m-1)+q(n-m, m), n>m>1; 正整数 n 的最大加数 n 1 不大于 m 的划分由 n 1 m-1 的划分和 n 1 =m 的划分组成 21

22 整数划分问题可以建立 q(n, m) 的如下递归关系 q( n, m) 1 n1, m1 q( n, n) n m 1 q( n, n 1) n m q( n, m 1) q( n m, m) n m 1 正整数 n 的划分数 p(n)=q(n, n) 22

23 整数划分问题可得算法伪代码为 : int q(int n, int m){ if ((n-1) (m<1)) return 0; if ((n==1) (m==1)) return 1; if (n<m) return q(n, n); if (n==m) return q(n, m-1)+1; return q(n, m-1)+q(n-m, m); } 23

24 整数划分问题的递归调用 q(6,6) q(6,5) 1 q(6,4) q(1,5) 1 q(6,3) q(2,4) q(6,2) q(3,3) = 3 q(2,2) 2 int q(int n, int m){ if ((n-1) (m<1)) return 0; if ((n==1) (m==1)) return 1; if (n<m) return q(n, n); if (n==m) return q(n, m-1)+1; return q(n, m-1)+q(n-m, m); } 1 q(6,1) q(4,2) q(6,6)= =11 1 q(4,1) q(2,2) 2 24

25 Hanoi 塔传说 25

26 Hanoi 塔问题设 A, B, C 是 3 个塔座开始时, 在塔座 A 上有一叠共 n 个圆盘, 这些圆盘自下而上, 由大到小地叠在一起各圆盘从小到大编号为 1,2,,n, 现要求将塔座 A 上的这一叠圆盘移到塔座 B 上, 并仍按同样顺序叠置在移动圆盘时应遵守以下移动规则 : 规则 1: 每次只能移动 1 个圆盘 ; 规则 2: 任何时刻都不允许将较大的圆盘压在较小的圆盘之上 ; 规则 3: 满足规则 1 和 2 的前提下, 可将圆盘移至 A,B,C 任一塔座上 26

27 递归算法算法 Hanoi(n, A, B, C) //n 个盘子 A 到 C 1. if n = 1 then move (A, C) 2. else Hanoi(n-1, A, C, B) 3. move (A, C) 4. Hanoi(n-1, B, A, C) 算法 Hanoi 以递归形式给出, 每个圆盘的具体移动方式并不清楚, 因此很难用手工移动来模拟这个算法 27

28 递归函数的运行轨迹在递归函数中, 调用函数和被调用函数是同一个函数注意递归函数的调用层次, 如果把调用递归函数的主函数称为第 0 层, 进入函数后, 首次递归调用自身称为第 1 层调用 ; 从第 i 层递归调用自身称为第 i+1 层反之, 退出第 i+1 层调用应该返回第 i 层采用图示方法描述递归函数的运行轨迹, 从中可较直观地了解到各调用层次及其执行情况 28

29 Hanoi 塔递归函数运行轨迹第 0 层 Hanio(3,A,B,C) 第 1 层 Hanio(2,A,C,B) Hanio(1,A,B,C) Move (A,B) 第 2 层 Hanio(1,A,B,C) Move (A,C) Hanio(1,C,A,B) Hanio(2,A,C,B) Hanio(1,C,A,B) Move (C,B) Move (A,C) Hanio(2,B,A,C) Hanio(1,B,C,A) Hanio(1,B,C,A) Move (B,A) Hanio(2,B,A,C) Move (B,C) Hanio(1,A,B,C) 结束 Hanio(1,A,B,C) Move (A,C) 29

30 递归算法算法 Hanoi(n, A, B, C) //n 个盘子 A 到 C 1. if n = 1 then move (A, C) 2. else Hanoi(n-1, A, C, B) 3. move (A, C) 4. Hanoi(n-1, B, A, C) 如果用了递归, 就找不到 while/for 循环语句此时, 该如何算时间复杂度呢? 30

31 递归算法算法 Hanoi(n, A, B, C) //n 个盘子 A 到 C 1. if n = 1 then move (A, C) 2. else Hanoi(n-1, A, C, B) 3. move (A, C) 4. Hanoi(n-1, B, A, C) 设 n 个盘子的移动次数为 T(n) T(n)=2T(n-1)+1 递推方程 T(1)=1 31

32 递推方程设序列 a 0,a 1,,a n, 简记为 {a n }, 一个把 a n 与某些个 a i (i<n) 联系起来的等式叫做关于序列 {a n } 的递推方程递推方程的求解 : 给定关于序列 {a n } 的递推方程和若干初值, 计算 a n 32

33 换元迭代法求解递推方程不断用递推方程的右部替换左部每次替换, 随着 n 的降低在和式中多出一项直到出现初值停止迭代将初值代入并对和式求和可用数学归纳法验证解的正确性 33

34 Hanoi 塔算法 T(n)=2T(n-1)+1 =2[2T(n-2)+1]+1 =2 2 T(n-2)+2+1 = =2 n-1 T(1)+2 n-2 +2 n =2 n-1 +2 n-1-1 =2 n -1 T(n)=2T(n-1)+1 T(1)=1 34

35 解的正确性 - 归纳验证证明 : 下述递推方程的解是 T(n)=2 n -1 T(n)=2T(n-1)+1 T(1)=1 方法 : 数学归纳法证 n=1, T(1)=2 1-1=1 假设对于 n, 解满足方程, 则 T(n+1) =2T(n)+1=2(2 n -1)+1=2 n

36 Hanoi 塔算法 T(n)=2T(n-1)+1 =2[2T(n-2)+1]+1 =2 2 T(n-2)+2+1 = =2 n-1 T(1)+2 n-2 +2 n =2 n-1 +2 n-1-1 =2 n -1 T(n)=2T(n-1)+1 T(1)=1 问题 : 如果 1 秒移动 1 个,64 个金蝶要多少时间? 5000 亿年!!! 36

37 每秒能算 60 万亿次要计算三天左右 37

38 Hanoi 塔算法有没有更好的算法??? 没有!!! 这是一个难解的问题, 不存在多项式时间的算法! 38

39 递归的函数调用 ( 回顾 C 语言 ) 39

40 递归的函数调用实现递归调用的关键是建立递归调用工作栈在调用算法之前 : 将所有实参指针, 返回地址等信息传递给被调用算法 ; 为被调算法的局部变量分配存储区 ; 将控制移到被调算法的入口返回调用算法时, 系统要完成 : 保存被调算法的结果 ; 释放分配给被调用算法的数据区 ; 依保存的返回地址将控制转移到调用算法 ; 40

41 递归小结优点 : 结构清晰, 可读性强, 而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法调试程序带来很大方便缺点 : 递归算法的运行效率较低, 无论是耗费的计算时间还是占用的存储空间都比非递归算法要多 41

试卷

( 试题中凡主观题答案意思对即可, 若与答案不同而言之成理, 亦可酌情给分 ) 一 ~ 二 (45 分 ) 1.B( 原文并未说网络社会生态系统的核心与现实社会生态系统的核心不同 ) 2.D( 服务网络收集到的数据要和关系网络的数据整合在一起,