算法及其基础.ppt

标题,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第一章 算法及其基础,1.1,引子,1.2,算法的基本概念,1.3,算法设计的一般过程,1.4,算法分析,1.5,相关基础,本章的要点与难点,要点,:,理解算法的概念。程序与算法的区别和联系；,理解算法设计的一般过程；,掌握用,C+/JAVA,语言以及伪代码描述算法的方法；,掌握算法的计算复杂性概念及分析。,难点,:,算法的计算复杂性（主要指时间复杂性）分析。,1.1,引子,排序问题,排序问题描述：,输入,：数字序列,X=,输出,：一个排列,X,=,，数字序列,X,和排列,X,之间为满射或一一映射（即元素一一对应），并且有,a,1,a,2,a,n,（元素间非减序）。,例如：,输入：,8,2,4,9,3,6,输出：,2,3,4,6,8,9,排序方法：,冒泡、,插入,、,归并,、二叉树、桶排序等。稳定的；,选择、,Shell,、堆、快速、组合排序等，不稳定的。,1.1,引子,插入排序,原理：,通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入,。,伪代码：,INSERTION-SORT(A,n)/A1.n,for j=2 to n,do key=Aj,i=j-1,while i 0 and Ai key,do Ai+1=Ai,i=i-1,Ai+1=key,1.1,引子,插入排序,示例：,1.1,引子,插入排序,证明,基于循环不变式,(Loop Invariant),：,循环不变式：,在每次循环迭代之前，子数组,A1.j-1,已包含了最初位于,A1.j-1,、但已排好序的各个元素。,初始化,：第一轮迭代之前（即,j=2,），子数组,A1.j-1,（即,A1,）显然保持了循环不变式；,保持,：假设第,j,次迭代之前循环不变式为真。该算法的第,j,次操作只是将,Aj,与已有序的,A1.j-1,中的元素进行比较，找到合适位置并插入。,j+1,次迭代之前，很显然,A1.(j+1)-1,也保持了循环不变式；,终止,：,j=n+1,时，显然,A1.(n+1)-1,（即,A1.n,）已包含了最初位于,A1.n,、且已排好序的各个元素。,1.1,引子,插入排序,运行时间分析：,最坏情况,：,T(n)=O(n,2,),。，算术级数。已非升序排序；,平均情况,：,T(n)=O(n,2,),。,，算术级数；,最好情况：,T(n)=O(n),。，已升序排序。,1.1,引子,归并排序,原理：,基于分而治之思想，递归地把待排序序列分解为若干子序列并进行排序，再把已排序的子序列合并为整体有序序列，最终实现全序列的有序。,伪代码：,MERGE-SORT(A,low,high)/A1.n,if low high,then mid=(low+high)/2,MERGE-SORT(A,low,mid),MERGE-SORT(A,mid+1,high),MERGE(A,low,mid,high),1.1,引子,归并排序示例,MERGE-SORT,：,1.1,引子,归并排序,(MERGE),MERGE,：,1.1,引子,归并排序,证明：,可以尝试采用循环不变式自行证明，这里略。,1.1,引子,归并排序,运行时间分析：,算法,(Algorithm),：,对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列。,算法的特性：,输入,（,0,个或多个）、,输出,（至少,1,个）、,确定性,（无歧义）、,有限性、可行性。,描述方式：,自然语言、图形、程序设计语言、伪代码,本书采用了面向对象程序设计语言,C+,，讲授时采用伪代码。,算法与程序的区别？,1.2,算法的基本概念,算法,程序,(Program),程序是算法用某种程序设计语言的具体实现；,程序可以不满足算法的性质,(4),。例如：,操作系统是一个在无限循环中执行的程序，因而其不是一个算法；,操作系统的各种任务：可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。,1.2,算法的基本概念,程序,会场安排问题、单源最短路径、哈夫曼编码、最小生成树,排序与查找、循环赛日程表,最长公共子序列、矩阵连乘、凸多边形最优三角剖分、加工顺序等,N,后、最大团、图的,m,着色,0-1,背包、,TSP,、布线问题,等等,1.2,算法的基本概念,经典问题,1.2,算法的基本概念,拼图游戏,在,n,n,格的棋盘上放置彼此不受攻击的,n,个皇后：,按照国际象棋的规则，皇后可以攻击与之处在 同一行 或 同一列 或 同一斜线 上的棋子；,n,后问题等价于在,n,n,格的棋盘上放置,n,个皇后，任何,2,个皇后不放在同一行或同一列或同一斜线上。,1 2 3 4 5 6 7 8,1,2,3,4,5,6,7,8,Q,Q,Q,Q,Q,Q,Q,Q,1.2,算法的基本概念,N,后问题,1.2,算法的基本概念,0-1,背包问题,起点,XXXXX,XXXXX,XXXXX,XXXXX,终点,XXXXX,1.2,算法的基本概念,布线问题,1.3,算法设计的一般过程,THANK YOU,SUCCESS,2025/8/18 周一,21,可编辑,算法复杂性（亦称算法复杂度）为算法运行时所需计算机资源的度量：,时间复杂性,（影响因素包括问题规模,n,、输入序列,I,、算法本身,A,）：,T(n,I,A),T(n),空间复杂性,（影响因素包括输入输出数据,IO,、辅助变量,V,、算法本身,A,）：,S(IO,V,A),S(V),很显然：,算法所需资源越多，算法的复杂性就越高；,算法所需资源越少，算法的复杂性就越低。,1.4,算法分析,算法复杂性,算法分析：,对算法的时间复杂性和空间复杂性进行分析，这里主要还是指对算法的时间复杂性的分析。,方法,：事后统计 和 事前分析,算法分析的意义：,算法设计,：复杂性尽可能的低；,算法选用,：选择复杂性最低的算法；,算法改进,：算法分析有助于算法的改进。,1.4,算法分析,影响算法运行时间的因素（除算法本身外）：,机器；,采用语言及编译程序；,编程能力等。,算法分析无需具体时间（精确或近似）：,针对同一问题不同算法的比较，相对而非绝对；,应该独立于机器及实现语言；,无论科技如何发展，其运行时间的测度应始终成立；,关心的是大的问题规模时的运行情况。,渐近复杂性,1.4,算法分析,算法渐近复杂性态：,设算法的运行时间为,T(n),，如果存在,T*(n),，使得,就称,T*(n),为算法的渐近性态或渐近时间复杂性。,1.4,算法分析,算法渐近复杂性态,?,假设算法,A,的运行时间表达式为,T,1,(n),：,T,1,(n)=30n,4,+20n,3,+40n,2,+46n+100,T*,1,(n),n,4,（阶）,假设算法,B,的运行时间表达式为,T,2,(n),：,T,2,(n)=1000n,3,+50n,2,+78n+10,T*,2,(n),n,3,（阶）,1.4,算法分析,算法渐近复杂性态示例,1.4,算法分析,几类阶的增长趋势,n,Log,2,n,n,nlog,2,n,n,2,n,3,2,n,n!,10,3.3,10,3.3*10,10,2,10,3,10,3,3.6*10,6,10,2,6.6,10,2,6.6*10,2,10,4,10,6,1.3*10,30,9.3*10,157,10,3,10,10,3,1.0*10,4,10,6,10,9,1.1*10,301,4*10,2567,增长趋势：,1,个基本操作花,1ns=10,-6,秒,1,年,=31536000,秒,=3.15*10,7,秒,渐近意义下的记号：,O,、,、,渐近上界,-O(big o),渐近下界,-(big),渐近精确界,-(big),o,、,和,1.4,算法分析,渐近复杂性记号,渐近上界,-O(big o):,设,f(N),和,g(N),是定义在正数集上的正函数，下同。,定义,：如果存在正的常数,C,和自然数,N0,，使得当,N,N0,时有,f(N),C,g(N),，则称函数,f(N),当,N,充分大时上有界，且,g(N),是它的一个上界，记为,f(N)=O(g(N),。,即,f(N),的阶,不高于,g(N),的阶。,求,T(n)=10n+4,的渐近上界,O,：,O(n),1.4,算法分析,渐近上界,根据,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),，则,(f)+O(g)=O(f),；,(5)O(cf(N)=O(f(N),，其中,c,是一个正的常数；,(6)f=O(f),。,1.4,算法分析,渐近上界,O,运算规则,常见的几类算法复杂性：,O(1),：常数阶；,O(,log,2,n,),O(n,log,2,n,),：对数阶；,O(,n,),O(,n,2,),O(,n,3,),O(,n,m,),：多项式阶。多项式时间算法；,O(,2,n,),O(,n!,),O(,n,n,),：指数阶。指数时间算法。,几类复杂性之间的关系：,O(1)O(,log,2,n,)O(,n,)O(n,log,2,n,)O(,n,)O(,n,2,)O(,n,3,),O(,n,m,)O(,2,n,)O(,n!,)1,，,f(n),为渐近正函数,记忆三种情况，见主定理。,1.4,算法分析,递归算法的复杂性分析,运行时间分析（归并排序算法）：,1.4,算法分析,递归树示例,1,运行时间分析：,1.4,算法分析,递归树示例,2,1.5,相关基础,数据结构：,顺序表与链表,栈与队列,树与图,集合,数学公式：,对数公式,组合公式,求和公式,向上取整和向下取整公式,THANK YOU,SUCCESS,2025/8/18 周一,41,可编辑,