《第1章 算法及基础知识精选文档.ppt》由会员分享，可在线阅读，更多相关《第1章 算法及基础知识精选文档.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章算法及基础知识本讲稿第一页，共四十五页教师简介v张阳张阳v信息工程学院信息工程学院v教学资源：作业管理系统教学资源：作业管理系统-张阳张阳本讲稿第二页，共四十五页课程简介v课时：理论课36+实验课12=48v成绩：平时30+考试70=100v平时：作业+实验+实验考核+考勤v教材：算法设计与分析王秋芬、吕聪颖等编著清华大学出版社2011年8月v参考v算法设计与分析王晓东第二版清华大学出版社（JAVA）v算法设计与分析王晓东第二版清华大学出版社（C/C+）本讲稿第三页，共四十五页课程简介学习算法的理由：学习算法的理由：一个人接受科技教育得到的最大收获，是一个人接受科技教育得到的最大收获，是
2、那些能够受用一生的一般性智能工具。那些能够受用一生的一般性智能工具。George Forsythe 计算机科学家到来以前我们做什么计算机科学家到来以前我们做什么1968n算算法是计算机科学的基石。没有算法，计算机程序将不复存在，法是计算机科学的基石。没有算法，计算机程序将不复存在，另外学习算法可以提高人们的分析能力。另外学习算法可以提高人们的分析能力。n算法可以看作是解决问题的一类特殊方法算法可以看作是解决问题的一类特殊方法它虽非问题的它虽非问题的答案，但它是经过准确定义的，用来获得答案的过程。答案，但它是经过准确定义的，用来获得答案的过程。n无论是否涉及计算机，特定的算法设计技术都能看作是问
3、题求解无论是否涉及计算机，特定的算法设计技术都能看作是问题求解的有效策略。的有效策略。本讲稿第四页，共四十五页课程简介算法的魅力：算法的魅力：思考思考 程序程序=算法算法+数据结构数据结构 算法让我们上一个更高的台阶算法让我们上一个更高的台阶要求要求:思考思考+预习预习/复习复习+实践实践上课：不旷课、不迟到上课：不旷课、不迟到本讲稿第五页，共四十五页课程简介n第1章算法及基础知识n第2章贪心法n第3章分治法n第4章动态规划n第5章搜索法n第6章随机化算法n第9章 NP完全理论本讲稿第六页，共四十五页第1章算法概述n学习要点:v理解算法的概念。v理解什么是程序，程序与算法的区别和内在联系。v掌
4、握算法的计算复杂性概念。v掌握用C+/JAVA语言描述算法的方法。本讲稿第七页，共四十五页第1章算法概述n算法：算法：v对于计算机科学来说，算法指的是对特定问题求解步骤的一种描对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列。述，是若干条指令的有穷序列。n算法的特性算法的特性v输入输入（0个或多个）、个或多个）、输出输出（至少（至少1个）、个）、确定性确定性（无歧义）、（无歧义）、有限性、可行性有限性、可行性n描述方式描述方式v自然语言、图形、程序设计语言、伪代码自然语言、图形、程序设计语言、伪代码v本书采用了面向对象程序设计语言本书采用了面向对象程序设计语言
5、C+n思考：算法与程序的区别？思考：算法与程序的区别？本讲稿第八页，共四十五页第1章算法概述n程序(Program)v程序是算法用某种程序设计语言的具体实现。v程序可以不满足算法的性质(4)。v操作系统：是一个在无限循环中执行的程序，因而不是一个算法。v操作系统的各种任务：可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。本讲稿第九页，共四十五页最大共约数求：非负整数求：非负整数M和和N的最大公约数，的最大公约数，记为：记为：Gcd(m,n)方法一：欧几里得算法方法一：欧几里得算法 Gcd(m,n)=Gcd(n,m mod n)Gcd(60,24)=Gcd(24,12
6、)=Gcd(12,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）找到（）找到（
7、1），（），（2）中的公因数。）中的公因数。（4）求公因数的积，该乘积为）求公因数的积，该乘积为m、n的最大公约数。的最大公约数。本讲稿第十页，共四十五页问题求解问题求解(Problem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法本讲稿第十一页，共四十五页算法设计n1理解问题n2了解计算机设备的性能n3在精确解法和近似解法间做选择n4确定适当的数据结构n5算法设计技术n6详细表述算法的方法n7证明算法的正确性n8分析算法n9为算法写代码本讲稿第十二页，共四十五页问题nN后问题n01背包问题n布线问题本讲稿第十三页，共四十五页n后问题在nn格
8、的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1234567812345678QQQQQQQQ本讲稿第十四页，共四十五页01背包问题本讲稿第十五页，共四十五页布线问题起点XXXXXXXXXXXXXXXXXXXX 终点XXXXX本讲稿第十六页，共四十五页n算法复杂性算法复杂性=算法运行时所需要的计算算法运行时所需要的计算机资源的量机资源的量v时间复杂性、空间复杂性时间复杂性、空间复杂性n影响时间复杂性的因素影响时间复杂性的因素v问题规模问题规模
9、n、输入序列、输入序列I、算法本身、算法本身An影响空间复杂性的因素影响空间复杂性的因素v算法本身、输入输出数据、辅助变量算法本身、输入输出数据、辅助变量n算法复杂性的权衡算法复杂性的权衡v时间复杂度和空间复杂度相互影响时间复杂度和空间复杂度相互影响v时间换空间或空间换时间时间换空间或空间换时间1.3算法分析本讲稿第十七页，共四十五页例：查找操作，三种情况例：查找操作，三种情况下的复杂性下的复杂性n最好情况Tmin（N)v1次n最坏情况Tmax（N)vN次n平均情况Tavg（N)v(N+1)/21.3算法分析本讲稿第十八页，共四十五页n算法渐近复杂性态算法渐近复杂性态设算法的运行时间为T(n)
10、，如果存在T*(n)，使得就称T*(n)为算法的渐进性态或渐进时间复杂性。1.3算法分析本讲稿第十九页，共四十五页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本讲稿第二十页，共四十五页渐近意义下的记号：渐近意义下的记号：O、o 设设f(N)和和g(N)是定义在正数集上的正函数。是定义在正数集上的正函数。nO的定义的定义：如果存在正的常数：如果存在正的常数C和自然数和自
11、然数N0，使得当，使得当N N0时有时有f(N)Cg(N)，则称函数，则称函数f(N)当当N充分大时充分大时上有界，且上有界，且g(N)是它的一个上界，记为是它的一个上界，记为f(N)=O(g(N)。n即即f(N)的阶不高于的阶不高于g(N)的阶。的阶。1.3算法分析本讲稿第二十一页，共四十五页1.3算法分析n求T(n)=10n+4的渐进上界vO(n)本讲稿第二十二页，共四十五页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)；(
12、4)如果如果g(N)=O(f(N)，则，则O(f)+O(g)=O(f)；(5)O(Cf(N)=O(f(N)，其中，其中C是一个正的常是一个正的常数；数；(6)f=O(f)。本讲稿第二十三页，共四十五页1.3算法分析增长次数：一年的秒数增长次数：一年的秒数=3.1536*107nLog2nnnlog2nn2n32nn!103.3103.3*101021031033.6*1061026.61026.6*1021041061.3*10309.3*10157103101031.0*104106109本讲稿第二十四页，共四十五页n：如果存在正的常数如果存在正的常数C和自然数和自然数N0，使得当，使得当N
13、 N0时有时有f(N)Cg(N)，则称函数，则称函数f(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)低，记为低
14、，记为f(N)=o(g(N)。1.3算法分析本讲稿第二十五页，共四十五页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)本讲稿第二十六页，共四十五页1.3算法分析n求T(n)=amnm+am-1nm-1+a1n+a0的上界、下界本讲稿第二十七页，共四十五页n算法复杂性是算法运行所需要的计算机资源的量算法复杂性是算法运行所需要的计算机资源的量n需要时间资源的量称为需要时间资源的量称为时间复杂性n需要的空间资源的量称为需要的空间资源的量称为空间复杂性空间复杂性
15、n用用N N、I I和和A A表示算法要解问题的规模、算法的输入和算法本身，表示算法要解问题的规模、算法的输入和算法本身，而且用而且用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算法分析本讲稿第二十八页，共四十五页n时间复杂度v例：求数组中元素最大值v例：查找元素n空间复杂度v例：插入法升序排序1.3算法分析本讲稿第二十九页，共四十五页1.3 算法分析算法分析n例：顺序搜索算法例：顺序搜索算法templateint seqSearch(Type*a,int n,Type k)for(int i=
16、0;in;i+)if(ai=k)return i;return-1;本讲稿第三十页，共四十五页算法分析的基本法则算法分析的基本法则n非递归算法：非递归算法：nfor/while循环v循环体内计算时间*循环次数；n嵌套循环v循环体内计算时间*所有循环次数；n顺序语句v各语句计算时间相加；nif-else语句vif语句计算时间和else语句计算时间的较大者。本讲稿第三十一页，共四十五页n子程序（或函数）直接调用自己或通过一系列调用语句间接调用自已，称为递归。直接或间接调用自身的算法称为递归算法。n采用递归算法来求解问题的一般步骤：v分析问题，寻找递归关系v找出停止条件v构建函数体1.4递归本讲稿第
17、三十二页，共四十五页菲波拉积数列本讲稿第三十三页，共四十五页n的阶乘停止条停止条件件递归递归关系关系两个要素 停止条件 递归关系Long long fun(int n)if(n0)printf(“illegal number!n”);break;else if(n=0)return 1;else return n*fun(n-1);本讲稿第三十四页，共四十五页排列问题n问题描述vn个元素，它们的编号为1,2,n，排列问题的目的是生成这n个元素的全排列。n解题步骤v分析递归关系v找出停止条件v设计递归函数本讲稿第三十五页，共四十五页排列问题n算法设计思路v将规模为n的排列问题转化为规模为n-1的
18、排列问题。v将规模为n-1的排列问题转化为规模为n-2的排列问题v将问题规模一级一级降至1，1个元素的排列是它本身，此时到达递推的停止条件。数组中的元素即为1个排列，然后进行回归依次得到其它的排列。本讲稿第三十六页，共四十五页排列问题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)。本讲稿第三十七页，共四十五页
19、排列问题voidperm(intA,intk,intn)/长度为n的A数组的后k个元素的全排列inti;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)的如下递归关系。的如下递归关系。整数划分本讲稿第四十二页，共四十五页整数划分问题整数划分问题在本例中，如果设在本例中，如果设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)。整数划分本讲稿第四十三页，共四十五页课后阅读n1.5基本数据结构v顺序表与链表v栈和队列v树和图v集合n1.6常用数学公式（p27-28）n阅读材料（算法界的十大名师）本讲稿第四十四页，共四十五页作业nP331-6,1-7本讲稿第四十五页，共四十五页