第1章 算法及基础知识精.ppt

《第1章 算法及基础知识精.ppt》由会员分享，可在线阅读，更多相关《第1章 算法及基础知识精.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章算法及基础知识第1页，本讲稿共45页教师简介v张阳张阳v信息工程学院信息工程学院v教学资源：作业管理系统教学资源：作业管理系统-张阳张阳第2页，本讲稿共45页课程简介v课时：理论课36+实验课12=48v成绩：平时30+考试70=100v平时：作业+实验+实验考核+考勤v教材：算法设计与分析王秋芬、吕聪颖等编著清华大学出版社2011年8月v参考v算法设计与分析王晓东第二版清华大学出版社（JAVA）v算法设计与分析王晓东第二版清华大学出版社（C/C+）第3页，本讲稿共45页课程简介学习算法的理由：学习算法的理由：一个人接受科技教育得到的最大收获，是一个人接受科技教育得到的最大收获，是那些能

2、够受用一生的一般性智能工具。那些能够受用一生的一般性智能工具。George Forsythe 计算机科学家到来以前我们做什么计算机科学家到来以前我们做什么1968n算算法是计算机科学的基石。没有算法，计算机程序将不复存在，法是计算机科学的基石。没有算法，计算机程序将不复存在，另外学习算法可以提高人们的分析能力。另外学习算法可以提高人们的分析能力。n算法可以看作是解决问题的一类特殊方法算法可以看作是解决问题的一类特殊方法它虽非问题的答案，但它虽非问题的答案，但它是经过准确定义的，用来获得答案的过程。它是经过准确定义的，用来获得答案的过程。n无论是否涉及计算机，特定的算法设计技术都能看作是问题无论

3、是否涉及计算机，特定的算法设计技术都能看作是问题求解的有效策略。求解的有效策略。第4页，本讲稿共45页课程简介算法的魅力：算法的魅力：思考思考 程序程序=算法算法+数据结构数据结构 算法让我们上一个更高的台阶算法让我们上一个更高的台阶要求要求:思考思考+预习预习/复习复习+实践实践上课：不旷课、不迟到上课：不旷课、不迟到第5页，本讲稿共45页课程简介n第1章算法及基础知识n第2章贪心法n第3章分治法n第4章动态规划n第5章搜索法n第6章随机化算法n第9章 NP完全理论第6页，本讲稿共45页第1章算法概述n学习要点:v理解算法的概念。v理解什么是程序，程序与算法的区别和内在联系。v掌握算法的计算

4、复杂性概念。v掌握用C+/JAVA语言描述算法的方法。第7页，本讲稿共45页第1章算法概述n算法：算法：v对于计算机科学来说，算法指的是对特定问题求解步骤的一种描对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列。述，是若干条指令的有穷序列。n算法的特性算法的特性v输入输入（0个或多个）、个或多个）、输出输出（至少（至少1个）、个）、确定性确定性（无歧义）、（无歧义）、有限性、可行性有限性、可行性n描述方式描述方式v自然语言、图形、程序设计语言、伪代码自然语言、图形、程序设计语言、伪代码v本书采用了面向对象程序设计语言本书采用了面向对象程序设计语言C+n思考：算

5、法与程序的区别？思考：算法与程序的区别？第8页，本讲稿共45页第1章算法概述n程序(Program)v程序是算法用某种程序设计语言的具体实现。v程序可以不满足算法的性质(4)。v操作系统：是一个在无限循环中执行的程序，因而不是一个算法。v操作系统的各种任务：可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。第9页，本讲稿共45页最大共约数求：非负整数求：非负整数M和和N的最大公约数，的最大公约数，记为：记为：Gcd(m,n)方法一：欧几里得算法方法一：欧几里得算法 Gcd(m,n)=Gcd(n,m mod n)Gcd(60,24)=Gcd(24,12)=Gcd(12,

6、0)=12方法二：连续整数检测算法方法二：连续整数检测算法（1）将）将 min(m,n)的值赋给的值赋给t。（2）m除以除以t，如果余数为，如果余数为0，进入第，进入第3步，否则，进入第步，否则，进入第4步。步。（3）n除以除以t，如果余数为，如果余数为0，返回，返回t值，结束，否则，进入第值，结束，否则，进入第4步。步。（4）t=t-1，返回第，返回第2步。步。方法三：中学里计算方法三：中学里计算Gcd(m,n)的过程（用数学定义的方法）的过程（用数学定义的方法）（1）找到）找到m的所有质因数。的所有质因数。（2）找到）找到n的所有质因数。的所有质因数。（3）找到（）找到（1），（），（2）

7、中的公因数。）中的公因数。（4）求公因数的积，该乘积为）求公因数的积，该乘积为m、n的最大公约数。的最大公约数。第10页，本讲稿共45页问题求解问题求解(Problem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法第11页，本讲稿共45页算法设计n1理解问题n2了解计算机设备的性能n3在精确解法和近似解法间做选择n4确定适当的数据结构n5算法设计技术n6详细表述算法的方法n7证明算法的正确性n8分析算法n9为算法写代码第12页，本讲稿共45页问题nN后问题n01背包问题n布线问题第13页，本讲稿共45页n后问题在nn格的棋盘上放置彼此不受攻击

8、的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1234567812345678QQQQQQQQ第14页，本讲稿共45页01背包问题第15页，本讲稿共45页布线问题起点XXXXXXXXXXXXXXXXXXXX 终点XXXXX第16页，本讲稿共45页n算法复杂性算法复杂性=算法运行时所需要的计算算法运行时所需要的计算机资源的量机资源的量v时间复杂性、空间复杂性时间复杂性、空间复杂性n影响时间复杂性的因素影响时间复杂性的因素v问题规模问题规模n、输入序列、输入序列I、算法

9、本身、算法本身An影响空间复杂性的因素影响空间复杂性的因素v算法本身、输入输出数据、辅助变量算法本身、输入输出数据、辅助变量n算法复杂性的权衡算法复杂性的权衡v时间复杂度和空间复杂度相互影响时间复杂度和空间复杂度相互影响v时间换空间或空间换时间时间换空间或空间换时间1.3算法分析第17页，本讲稿共45页例：查找操作，三种情况例：查找操作，三种情况下的复杂性下的复杂性n最好情况Tmin（N)v1次n最坏情况Tmax（N)vN次n平均情况Tavg（N)v(N+1)/21.3算法分析第18页，本讲稿共45页n算法渐近复杂性态算法渐近复杂性态设算法的运行时间为T(n)，如果存在T*(n)，使得就称T*

10、(n)为算法的渐进性态或渐进时间复杂性。1.3算法分析第19页，本讲稿共45页1.3算法分析假设算法A的运行时间表达式为T1(n)T1(n)=30n4+20n3+40n2+46n+100假设算法B的运行时间表达式为T2(n)T2(n)=1000n3+50n2+78n+10算法A的运行时间可记为：T*1(n)n4算法B的运行时间可记为：T*2(n)n3第20页，本讲稿共45页渐近意义下的记号：渐近意义下的记号：O、o 设设f(N)和和g(N)是定义在正数集上的正函数。是定义在正数集上的正函数。nO的定义的定义：如果存在正的常数：如果存在正的常数C和自然数和自然数N0，使得，使得当当N N0时有时

11、有f(N)Cg(N)，则称函数，则称函数f(N)当当N充分充分大时上有界，且大时上有界，且g(N)是它的一个上界，记为是它的一个上界，记为f(N)=O(g(N)。n即即f(N)的阶不高于的阶不高于g(N)的阶。的阶。1.3算法分析第21页，本讲稿共45页1.3算法分析n求T(n)=10n+4的渐进上界vO(n)第22页，本讲稿共45页1.3算法分析根据根据O的定义，容易证明它有如下运算规则：的定义，容易证明它有如下运算规则：(1)O(f)+O(g)=O(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(

12、f)+O(g)=O(f)；(5)O(Cf(N)=O(f(N)，其中，其中C是一个正的常数；是一个正的常数；(6)f=O(f)。第23页，本讲稿共45页1.3算法分析增长次数：一年的秒数增长次数：一年的秒数=3.1536*107nLog2nnnlog2nn2n32nn!103.3103.3*101021031033.6*1061026.61026.6*1021041061.3*10309.3*10157103101031.0*104106109第24页，本讲稿共45页n：如果存在正的常数如果存在正的常数C和自然数和自然数N0，使得当，使得当N N0时有时有f(N)Cg(N)，则称函数，则称函数f

13、(N)当当N充分大时下有界，且充分大时下有界，且g(N)是它的一个下界，记为是它的一个下界，记为f(N)=(g(N)。即。即f(N)的阶不低于的阶不低于g(N)的阶。的阶。n：如果存在正的常数如果存在正的常数C1,C2和自然数和自然数N0，使得当，使得当N N0时时,有有C1g(N)f(N)C2g(N)，则称，则称g(N)和和f(N)同阶。同阶。no：对于任意给定的对于任意给定的0，都存在正整数，都存在正整数N0，使得当，使得当N N0时有时有f(N)/Cg(N),则称函数则称函数f(N)当当N充分大时充分大时的阶比的阶比g(N)低，记为低，记为f(N)=o(g(N)。1.3算法分析第25页，

14、本讲稿共45页1.3算法分析n求T(n)=30n4+20n3+40n2+46n+100的渐进下界v(n4)n求T(n)=20n2+8n+10的阶v(n2)n求T(n)=20n2+8n+10的阶v(n2)第26页，本讲稿共45页1.3算法分析n求T(n)=amnm+am-1nm-1+a1n+a0的上界、下界第27页，本讲稿共45页n算法复杂性是算法运行所需要的计算机资源的量算法复杂性是算法运行所需要的计算机资源的量n需要时间资源的量称为需要时间资源的量称为时间复杂性n需要的空间资源的量称为需要的空间资源的量称为空间复杂性空间复杂性n用用N N、I I和和A A表示算法要解问题的规模、算法的输入和

15、算法表示算法要解问题的规模、算法的输入和算法本身，而且用本身，而且用C C表示复杂性表示复杂性nC=F(N,I,A)C=F(N,I,A)nT=T(N,I)T=T(N,I)和和S=S(N,I)S=S(N,I)1.3算法分析第28页，本讲稿共45页n时间复杂度v例：求数组中元素最大值v例：查找元素n空间复杂度v例：插入法升序排序1.3算法分析第29页，本讲稿共45页1.3 算法分析算法分析n例：顺序搜索算法例：顺序搜索算法templateint seqSearch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;return-1;第30

16、页，本讲稿共45页算法分析的基本法则算法分析的基本法则n非递归算法：非递归算法：nfor/while循环v循环体内计算时间*循环次数；n嵌套循环v循环体内计算时间*所有循环次数；n顺序语句v各语句计算时间相加；nif-else语句vif语句计算时间和else语句计算时间的较大者。第31页，本讲稿共45页n子程序（或函数）直接调用自己或通过一系列调用语句间接调用自已，称为递归。直接或间接调用自身的算法称为递归算法。n采用递归算法来求解问题的一般步骤：v分析问题，寻找递归关系v找出停止条件v构建函数体1.4递归第32页，本讲稿共45页菲波拉积数列第33页，本讲稿共45页n的阶乘停止停止条件条件递归

17、关递归关系系两个要素 停止条件 递归关系Long long fun(int n)if(n0)printf(“illegal number!n”);break;else if(n=0)return 1;else return n*fun(n-1);第34页，本讲稿共45页排列问题n问题描述vn个元素，它们的编号为1,2,n，排列问题的目的是生成这n个元素的全排列。n解题步骤v分析递归关系v找出停止条件v设计递归函数第35页，本讲稿共45页排列问题n算法设计思路v将规模为n的排列问题转化为规模为n-1的排列问题。v将规模为n-1的排列问题转化为规模为n-2的排列问题v将问题规模一级一级降至1，1个

18、元素的排列是它本身，此时到达递推的停止条件。数组中的元素即为1个排列，然后进行回归依次得到其它的排列。第36页，本讲稿共45页排列问题n算法描述v使用递归技术来解决全排列问题。vperm(A,k,n)：生成数组A后面k个元素的排列。v当k=1时：得解v当1k=n时：可由算法Perm(A,k-1,n)生成数组A后面k-1个元素的排列v数组A后面k个元素的排列，需要逐一将数组第n-k个元素与数组中第n-kn-1个元素互换，每互换一次，就执行一次perm(A,k-1,n)。第37页，本讲稿共45页排列问题voidperm(intA,intk,intn)/长度为n的A数组的后k个元素的全排列inti;

19、if(k=1)for(i=0;in;i+)coutAi;elsefor(i=n-k;im1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1n-1 的划分组成。(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。整数划分问题整数划分问题如果问题本身都具有比较明显的递归关系，因而容易用递归函数如果问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。直接求解。在本例中，如果设在本例中，如果设p(n)p(n)为正整数为正整数n n的划分数，则难以找到递归关系，因此的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数考虑增加一

20、个自变量：将最大加数n n1 1不大于不大于m m的划分个数记作的划分个数记作q(n,m)q(n,m)。可以建立。可以建立q(n,m)q(n,m)的如下递归关系。的如下递归关系。整数划分第42页，本讲稿共45页整数划分问题整数划分问题在本例中，如果设在本例中，如果设p(n)p(n)为正整数为正整数n n的划分数，则难以找到递归关系，因此考的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数虑增加一个自变量：将最大加数n n1 1不大于不大于m m的划分个数记作的划分个数记作q(n,m)q(n,m)。可以建。可以建立立q(n,m)q(n,m)的如下递归关系。的如下递归关系。正整数正整数n n的划分数的划分数p(n)=q(n,n)p(n)=q(n,n)。整数划分第43页，本讲稿共45页课后阅读n1.5基本数据结构v顺序表与链表v栈和队列v树和图v集合n1.6常用数学公式（p27-28）n阅读材料（算法界的十大名师）第44页，本讲稿共45页作业nP331-6,1-7第45页，本讲稿共45页