《算法引论概要》由会员分享，可在线阅读，更多相关《算法引论概要（23页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析 （ACM/ICPC程序设计方法论）,广东江门五邑大学信息学院 高宏宾,2007年8月,主要内容介绍,第1章 算法引论 第2章 递归与分治策略 第3章 动态规划 第4章 贪心算法 第5章 回溯法 第6章 分支限界法 第7章 概率算法 第8章 NP完全性理论 第9章 近似算法 第10章 算法优化策略,第1章 算法引论,1.1 算法与程序 算法设计实例 例1. 按递增次序生成M的最小的n个元素，M定义为： 1 M xM， 则 y=2x+1 My=3x+ 1 M,本章主要知识点,1.1 算法与程序 1.2 表达算法的抽象机制 1.3 描述算法 1.4 算法复杂性分析,0 1 2 3 4
2、 5 6 7 8 9 p2p3 i,1 3 4 7 13,if(2*mp2=3*mp3) mi=2*mp2+1; p2+; p3+; else if(2*mp23*mp3) mi=2*mp2+1; p2+; else mi=3*mp3+1; p3+; i+;,算法核心,算法设计思想,#include #define s 100 main() int n,p2,p3,i,ms; m1=p2=p3=1; scanf(%d, ,#include #include #define eps 1e-6 main() float e,t; /* 当前项t */ int i,n; /* i的阶乘n */ e=
3、t=1.0; i=n=1; while(fabs(t)eps) e+=t; /* 加当前项 */ i+=1; n*=i; /* 计算i的阶乘 */ t=1/n; /* 计算下一项 */ printf(e=%fn,e); ,例2. 计算 e的值,例3. 螺旋方阵 的生成,10,13,11,12,25,21,20,19,18,17,16,15,14,9,8,7,6,5,4,3,2,1,24,23,22,#define M 64 main() int i,j,num,n,aMM; num=1; scanf(%d, ,例4. 方阵的旋转,10,13,11,12,25,21,20,19,18,17,16
4、,15,14,9,8,7,6,5,4,3,2,1,24,23,22,aij ji jn-i+1 an-i+1j,temp,for(j=i;jn-i+1;j+) temp=aij; aij=ajn-i-1; ajn-i-1=an-i-1n-j-1; an-i-1n-j-1=an-j-1i; an-j-1i=temp; ,#include #define M 64 main() int i,j,temp,n,aMM; scanf(%d, ,for(i=0;in;i+) for(j=0; jn; j+) printf(%d,aij); printf(n); ,例5. 幻方阵的生成,13,6,4,16
5、,14,7,5,23,15,17,24,8,2,1,19,12,10,22,20,25,18,9,11,3,21,#define M 64 main() int i,j,n,aMM; scanf(%d, ,for(i=0;in;i+) for(j=0; jn; j+) printf(%5d,aij); printf(n); ,2. 算法设计方法与实践,递归方法 分治方法 动态规划方法 贪心方法 回溯方法 分支限界方法 概率方法 NP完全性 近似方法 算法优化方法,3. 算法的概念,算法是为解决某个特定问题而设计的由一些命令组成的序列，该序列具备5大特征： 1.有穷性 算法中命令的个数是有限的；
6、每个命令 的执行时间是有限的。 2.确定性 算法中每个命令的含义是确切的。 3.有效性 算法中每个命令是可行的。 4.输入 算法需要从外界接受数据,且个数0。 5.输出 算法必须产生一组数据作为其结果，且 个数0。,4. 简单算法举例,例6. 计算12345的值。 推广：计算 i (i=1,n) 的值。 分析：为了计算 12 (i-1) i (i+1) n，我们不妨设 p= 12 i 并称p为部分积。此时，对于当前的i,若做操作 i+1i, 然后对部分积p做操作 p i p，则p的值顺增一个因子。因此，反复进行 i+1i ；p i p；可使p逐渐接近计算目标。再考虑 p，i 的初始状态以及能够
7、进行上述操作的条件，可以设计出如右所示算法：,S0: 输入n； S1: 1 p; S2: 0 i; S3: i+1i; S4: p i p; S5: if i n then goto S3; else output p; 要点:部分积的概念及其表示; 循环变量及其增量的确定; 进入循环的初始值的确定; 退出循环的条件。,类比：计算i (i=1,n)的值 S0: 输入n； S1: 0 s; S2: 0 i; S3: i+1i; S4: s + i s; S5: if i n then goto S3; else output s;,要点: 部分和的概念及其表示; 循环变量及其增量的确定; 进入循
8、环的初始值的确定; 退出循环的条件。,例7. 判断20002500年中的每一年是否是闰年? 此问题的算法设计思路: 假设year是年份,则: S1: year=2000; S2: 如果 year 是闰年 则 输出year “是闰年”; 否则 输出year “不是闰年”; S3: year=year+1; S4: 如果 year=2500 则 转向S2; 否则 终止该算法;,要点: 逐步求精_逐步细化。,例8. 计算(-1)/i (a=i+1,i=1,n) 的值 问题的性质:部分和问题,S0: 输入n； S1: 1sign; S2: 1sum; S3: 2 deno; S4: (-1) sign
9、sign; 产生当前项符号 S5: sign (1/deno) term; 生成当前项 S6: sum+term sum; 累加当前项 S7: deno+1 deno; 产生下一项的分母 S8: if deno = n 要点:当前项正负号的转换 then goto S4; else output sum;,1.2 表达算法的抽象机制,1.从机器语言到高级语言的抽象,高级程序设计语言的主要好处是：,（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。,（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周
10、时间的培训就可以胜任程序员的工作；,（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；,（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；,2.抽象数据类型,抽象数据类型是算法的一个数据模型连同定义在该模型上 并作为算法构件的一组运算。,抽象数据类型带给算法设计的好处有：,（1）算法顶层设计与底层实现分离； （2）算法设计与数据结构设计隔开，允许数据结构自由选择； （3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷； （4）用抽象数据类型表述的算法具有很好的可维护性； （
11、5）算法自然呈现模块化； （6）为自顶向下逐步求精和模块化提供有效途径和工具； （7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。,1.3 算法的描述,1. 自然语言描述 问题： 二义性问题。 例：1. 张先生对李先生讲他的儿子考上了大学。 2. 下雨天留客天留我不留 2. 流程图描述 结论：用三种控制结构可以描述一切可计算的问题。 3. 改进的流程图描述 原则：单一出入口原则。 4. N-S流程图描述,S1,S2,S1,S2,S,con,con,S1 S2,y con n S1 S2,While con S,S until con,S,con,5. 伪代码描述 6. 程序设计
12、语言描述 产生用程序设计语言描述的算法程序是程序设计 的最终目标。,1.4 算法复杂性分析,算法复杂性是算法运行所需要的计算机资源的量，需 要时间资源的量称为时间复杂性，需要空间资源的量称为 空间复杂性。这个量应该是只依赖于算法要解的问题的规 模、算法的输入和算法本身的函数。如果分别用N、I和A 表示算法要解问题的规模、算法的输入和算法本身，而且 用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间 复杂性和空间复杂性分开，并分别用T和S来表示，则 有： T=T(N,I)和S=S(N,I) 。（通常，让A隐含在复杂性函 数名当中）,最坏情况下的时间复杂性：,最好情况下的时间复杂性：,平
13、均情况下的时间复杂性：,其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*) 达到Tmax(N)的合法输入； 是中使T(N, )达到Tmin(N)的合法 输入；而P(I)是在算法的应用中出现输入I的概率。,算法复杂性在渐近意义下的阶：,渐近意义下的记号：O、o 设f(N)和g(N)是定义在正数集上的正函数。,O的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)。即f(N)的阶不高于g(N)的阶。,根据O的定义，容易证明它有如下运算规则： (1)O(f)+O(g)=O(
14、max(f,g)； (2)O(f)+O(g)=O(f+g)； (3)O(f)O(g)=O(fg)； (4)如果g(N)=O(f(N)，则O(f)+O(g)=O(f)； (5)O(Cf(N)=O(f(N)，其中C是一个正的常数； (6)f=O(f)。,的定义：如果存在正的常数C和自然数N0，使得当NN0时 有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它 的一个下界，记为f(N)=(g(N)。即f(N)的阶不低于g(N)的阶。,的定义：定义f(N)= (g(N)当且仅当f(N)=O(g(N)且 f(N)= (g(N)。此时称f(N)与g(N)同阶。,o的定义：对于任意给定的0，都存在正整数N0，使得 当NN0时有f(N)/Cg(N),则称函数f(N)当N充分大时的阶比 g(N)低，记为f(N)=o(g(N)。 例如，4NlogN+7=o(3N2+4NlogN+7)。,
