算法及基础知识.ppt

算法分析,张阳 信息工程学院,教师简介,张阳信息工程学院109教学资源：作业管理系统-张阳,课程简介,课时：理论课36+实验课12=48成绩：平时30+考试70=100平时：作业+实验+实验考核+考勤教材：算法设计与分析王秋芬、吕聪颖等编著 清华大学出版社 2011年8月参考算法设计与分析 王晓东 第二版 清华大学出版社（JAVA）算法设计与分析 王晓东 第二版 清华大学出版社（C/C+）,课程简介,学习算法的理由：一个人接受科技教育得到的最大收获，是那些能够受用一生的一般性智能工具。George Forsythe 计算机科学家到来以前我们做什么1968算法是计算机科学的基石。没有算法，计算机程序将不复存在，另外学习算法可以提高人们的分析能力。算法可以看作是解决问题的一类特殊方法它虽非问题的答案，但它是经过准确定义的，用来获得答案的过程。无论是否涉及计算机，特定的算法设计技术都能看作是问题求解的有效策略。,课程简介,算法的魅力：思考 程序=算法+数据结构 算法让我们上一个更高的台阶要求:思考+预习/复习+实践上课：不旷课、不迟到,课程简介,第1章算法及基础知识第2章贪心法第3章分治法第4章动态规划第5章搜索法第6章随机化算法第9章 NP完全理论,第1章 算法概述,学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握用C+/JAVA语言描述算法的方法。,第1章 算法概述,算法：对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列。算法的特性输入（0个或多个）、输出（至少1个）、确定性（无歧义）、有限性、可行性描述方式自然语言、图形、程序设计语言、伪代码本书采用了面向对象程序设计语言C+思考：算法与程序的区别？,第1章 算法概述,程序(Program)程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。操作系统：是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务：可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。,最大共约数,求：非负整数M和N的最大公约数，记为：Gcd(m,n)方法一：欧几里得算法 Gcd(m,n)=Gcd(n,m mod n)Gcd(60,24)=Gcd(24,12)=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）找到（1），（2）中的公因数。（4）求公因数的积，该乘积为m、n的最大公约数。,问题求解(Problem Solving),算法设计,1理解问题2了解计算机设备的性能3在精确解法和近似解法间做选择4确定适当的数据结构5算法设计技术6详细表述算法的方法7证明算法的正确性8分析算法9为算法写代码,问题,N后问题01背包问题布线问题,n后问题,在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。,01背包问题,布线问题,算法复杂性=算法运行时所需要的计算机资源的量时间复杂性、空间复杂性影响时间复杂性的因素问题规模n、输入序列I、算法本身A影响空间复杂性的因素算法本身、输入输出数据、辅助变量算法复杂性的权衡时间复杂度和空间复杂度相互影响时间换空间或空间换时间,1.3 算法分析,例：查找操作，三种情况下的复杂性最好情况Tmin（N)1次最坏情况Tmax（N)N次平均情况Tavg（N)(N+1)/2,1.3 算法分析,算法渐近复杂性态设算法的运行时间为T(n)，如果存在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)是定义在正数集上的正函数。O的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)。即f(N)的阶不高于g(N)的阶。,1.3 算法分析,1.3 算法分析,求T(n)=10n+4的渐进上界O(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)；(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*107,：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=(g(N)。即f(N)的阶不低于g(N)的阶。：如果存在正的常数C1,C2和自然数N0，使得当NN0时,有C1g(N)f(N)C2g(N)，则称g(N)和f(N)同阶。o：对于任意给定的0，都存在正整数N0，使得当NN0时有f(N)/Cg(N),则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g(N)。,1.3 算法分析,1.3 算法分析,求T(n)=30n4+20n3+40n2+46n+100的渐进下界(n4)求T(n)=20n2+8n+10的阶(n2)求T(n)=20n2+8n+10的阶(n2),1.3 算法分析,求T(n)=amnm+am-1nm-1+a1n+a0的上界、下界,算法复杂性是算法运行所需要的计算机资源的量需要时间资源的量称为时间复杂性需要的空间资源的量称为空间复杂性用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性C=F(N,I,A)T=T(N,I)和S=S(N,I),1.3 算法分析,时间复杂度例：求数组中元素最大值例：查找元素空间复杂度例：插入法升序排序,1.3 算法分析,1.3 算法分析,例：顺序搜索算法,templateint seqSearch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;return-1;,算法分析的基本法则,非递归算法：for/while 循环循环体内计算时间*循环次数；嵌套循环循环体内计算时间*所有循环次数；顺序语句各语句计算时间相加；if-else语句if语句计算时间和else语句计算时间的较大者。,子程序（或函数）直接调用自己或通过一系列调用语句间接调用自已，称为递归。直接或间接调用自身的算法称为递归算法。采用递归算法来求解问题的一般步骤：分析问题，寻找递归关系找出停止条件构建函数体,1.4 递归,菲波拉积数列,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个元素，它们的编号为1,2,n，排列问题的目的是生成这n个元素的全排列。解题步骤分析递归关系找出停止条件设计递归函数,排列问题,算法设计思路将规模为n的排列问题转化为规模为n-1的排列问题。将规模为n-1的排列问题转化为规模为n-2的排列问题 将问题规模一级一级降至1，1个元素的排列是它本身，此时到达递推的停止条件。数组中的元素即为1个排列，然后进行回归依次得到其它的排列。,排列问题,算法描述使用递归技术来解决全排列问题。perm(A,k,n)：生成数组A后面k个元素的排列。当k=1时：得解当1k=n时：可由算法Perm(A,k-1,n)生成数组A后面k-1个元素的排列数组A后面k个元素的排列，需要逐一将数组第n-k个元素与数组中第n-kn-1个元素互换，每互换一次，就执行一次perm(A,k-1,n)。,排列问题,void perm(int A,int k,int n)/长度为n的A数组的后k个元素的全排列 int i;if(k=1)for(i=0;in;i+)coutAi;else for(i=n-k;in;i+)swap(Ai,An-k);perm(A,k-1,n);swap(Ai,An-k);,时间复杂度：采用后向代入法计算可得到通项公式：T(n)=nT(n-1)=.=n(n-1)(n-2).2T(1)=n!时间复杂度：O(n!),排列问题,递归算法的空间复杂度：算法的递归深度全排列算法perm共执行了n次递归深度为n空间复杂度：O(n),排列问题,整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+nk，其中n1n2nk1，k1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。例如：正整数6有如下11种不同的划分：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。,整数划分,(2)q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。,(1)q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即,(4)q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1n-1 的划分组成。,(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。,整数划分问题如果问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,整数划分,整数划分问题在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,正整数n的划分数p(n)=q(n,n)。,整数划分,课后阅读,1.5 基本数据结构顺序表与链表栈和队列树和图集合1.6 常用数学公式（p27-28）阅读材料（算法界的十大名师）,作业,P33 1-6,1-7,