算法分析的基本概念和方法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,1,章 算法分析的基本概念和方法,内容提要,一、算法及其特性,二、算法的时间空间复杂度,三、算法分析,(Algorithm Analysis),1.,分析算法时间复杂度的基本步骤,2.,算法时间复杂度的有关概念,3.,分析、求解算法复杂度的方法,四、最优算法,(optimal algorithm),知识要点,算法分析的概念,复杂度渐近表示的记号：,O,平均时间复杂度，最坏时间复杂度，最好时间复杂度,最优算法,分析算法复杂度的基本方法,分析算法时间复杂度的步骤,基本运算执行频数的统计方法,数学知识：求和公式、定积分近似求和、递归方程的求解,学习要求,掌握算法复杂度的基本概念,熟悉算法复杂度分析的基本方法,1.1,算法及其特性,一、算法,(algorithm),算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。,二、算法的五个特性,确定性,能行性,有穷性,输入,输出,1.1,算法及其特性,衡量算法性能一般有下面几个标准：,确定性,易读性,健壮性,算法的时间和空间性能：高效率和低存储空间,本课程中主要讨论算法的时间和空间性能，并以此作为衡量算法性能的重要标准，而且主要侧重于时间方面。,三、衡量算法性能的标准,1.2.,算法的时间空间复杂度,算法的时间复杂度：在算法运行期间所花费的时间。,通常用渐进形式表示。比如，,T(n,)=O(n2),、,(n2),或,(n2),一、算法的时间复杂度,(Time Complexity),1.2.,算法的时间空间复杂度,算法的空间复杂度：在算法运行期间所需要的内存空间，通常指除开容纳输入数据之外的附加空间（,auxiliary space,or work space,）。,通常用渐进形式表示。比如，,S(n,)=O(,n,2),、,(,n,2),或,(,n,2),二、算法的空间复杂度,(Space Complexity),1.2.,算法的时间空间复杂度,算法分析是指对于计算机算法的时间和空间复杂度进行定量的分析。为了确切起见，假定执行算法的计算机是满足如下条件的“通用型”计算机：,顺序处理机：每次执行程序中的一条指令；,RAM,足够大；,在固定的时间内可把一个数从一个单元取出或者存入。,下面将学习算法分析的主要内容：,分析算法时间复杂度的基本步骤,算法时间复杂度的有关概念,分析、求解算法复杂度的数学知识,三、算法分析,(Algorithm Analysis),1.3.,分析复杂度的基本步骤,对算法的分析必须脱离具体的计算机结构和程序设计语言。因此，比较两个算法的好坏，看其中所需的运算时间的长短是由算法所需的运算次数决定的。任何一个算法都可能有几种运算，因此，我们抓住其中影响算法运行时间最大的运算作为基本运算。如在一个字表中寻找,Z,的问题，把,Z,和表中元素的比较作为基本运算。两个实数矩阵相乘的问题中，则把两个实数相乘作为基本运算。,一、选取一种运算作为基本运算,(basic operation),1.3.,分析复杂度的基本步骤,一个计算步骤，如果其时间耗费总是不超过某个常量，而与输入和算法无关，则称之为元运算。,元运算,(elementary operation),常见的元运算,算术运算：加、减、乘、除；,比较和逻辑运算；,赋值运算，包括指针赋值（比如，在遍历表或树时的指针赋值）；等等。,1.3.,分析复杂度的基本步骤,同一个问题对不同的输入，基本运算的次数亦可能不同。因此，我们引进问题大小（即规模，,size,）的概念。例如，在一个姓名表中寻找给定的,Z,的问题，问题的大小可用表中姓名的数目表示。对于两个实数矩阵相乘的问题，其大小可用矩阵的阶来表示。而对于遍历一棵二叉树的问题，其大小是用树中结点数来表示等等。这样，一个算法的基本运算的次数就可用问题的大小,n,的函数,f(n,),来表示。,二、表示出在算法运行期间基本运算执行的总频数,1.3.,分析复杂度的基本步骤,在一个算法中，出现的频数最高（在相差一个常数因子的意义上）的元运算称为基本元算。,基本运算,(basic operation),常见的基本运算,当分析查找和排序的算法时，如果元素的比较是元运算，则可作为基本运算；,在矩阵乘法的算法中，数的乘法可作为基本运算；,当遍历链表时，给指针赋值或者更新指针的操作可作为基本运算；,在图的遍历中，可以将访问节点的操作为基本运算；等等。,1.3.,分析复杂度的基本步骤,在实际中精确地求一个算法的基本运算次数,f(n,),等于多少，往往不容易，甚至有时根本不可能，有些即使求出结果很长，很繁琐，不易比较，需要简化。这时候我们可以不精确地估计,f(n,),。此外，我们分析算法的时间目的主要在于，能区分不同算法的优劣，在,n,很小时候，差别不大，随着,n,的逐渐增大，差别越来越大，是个极限行为。基于上述原因，引进下面渐近表示的方法。复杂度渐近表示可以将简洁地表示出复杂度的数量级别。,三、渐近时间复杂度,(asymptotic time complexity),1.3.,分析复杂度的基本步骤,设,f(n,),和,g(n,),均是从自然数集到非负实数集上的函数。如果存在常数,c0,和一个自然数,n0,，使得对于任意的,nn0,，均有,f(n)cg(n,),则,f(n,)=,O(g(n,),。,含义：阶至多为,g(n,),的函数，即上限。,读法：,O(g(n,),读作“大,Oh,g(n,)”,。,1.O-,记号,1.3.,分析复杂度的基本步骤,设,f(n,),和,g(n,),均是从自然数集到非负实数集上的函数。如果存在常数,c0,和一个自然数,n0,，使得对于任意的,nn0,，均有,f(n)cg(n,),则，,f(n,)=,(,g(n,),。,含义：阶至少为,g(n,),的函数，即下限。,读法：,(,g(n,),读作“,omega,g(n,)”,。,2.,-,记号,1.3.,分析复杂度的基本步骤,设,f(n,),和,g(n,),均是从自然数集到非负实数集上的函数。如果存在一个自然数,n0,和两个正常数,c1,，,c2,，使得对于任意的,nn0,，均有,c1g(n)f(n)c2g(n),则，,f(n,)=,(,g(n,),。,含义：阶恰好为,g(n,),的函数。,读法：,(,g(n,),读作“,theta,g(n,)”,。,3.,-,记号,1.3.,分析复杂度的基本步骤,例,1,设,f(n,)=10n2+20n,。则有,f(n,)=O(n2),f(n,)=,(n2),f(n,)=,(n2),例,2,设,f(n,)=aknk+ak-1nk-1+a1n+a0,(,ak,0),。则有,f(n,)=,O(nk,),f(n,)=,(,nk,),f(n,)=,(,nk,),四、举例,1.3.,分析复杂度的基本步骤,例,3,设,f(n,)=2,n,，,g(n,)=n!,。则有,f(n,)=,O(g(n,),但是，,f(n),(g(n,),因此，,f(n,),(,g(n,),此时，记作,O(f(n,),O(g(n,),。,四、举例,1.3.,分析复杂度的基本步骤,各种复杂度比较示意图如下。,五、复杂度比较示意图,1.3.,分析复杂度的基本步骤,各种复杂度比较示意图如下。,五、复杂度比较示意图,1.4.,复杂度的有关概念,一、算法时间复杂度,对于算法的时间复杂度，通常从分平均、最坏、最好几种情形来衡量，尤其是前两种。,算法的平均复杂性 设,Dn,是对于所考虑问题来说大小为,n,的输入的集合，并设,i,是,Dn,的一个元素，,p(i,),是,i,出现的概率，,t(i,),是算法在输入,i,时所执行的基本运算次数。那么，算法的平均复杂性定义为：,A(n,)=,iDn,p(i)t(i,),算法的最坏复杂性,W(n,)=MAX,iDn,t(i,),算法的最好复杂性,B(n,)=MIN,iDn,t(i,),1.4.,复杂度的有关概念,例,1,检索问题的顺序查找算法,1.1,。以元素的比较作为基本操作。考虑成功检索的情况。,最好情况下的时间复杂度：,(1),最坏情况下的时间复杂度：,(,n,),在等概率前提下，平均情况下的时间复杂度：,(,n,),二、举例,算法分析方法,例：顺序搜索算法,template,int,seqSearch(Type,*a,int,n,Type k),for(int,i=0;i,n;i,+),if(,ai,=k)return i;,return-1;,（,1,）,T,max,(,n,)=max,T,(i,)|,size(i,)=,n,=,O,(,n,),（,2,）,T,min,(,n,)=min,T,(i,)|,size(i,)=,n,=,O,(1),（,3,）在平均情况下，假设：,(a),搜索成功的概率为,p,(0,p,1),；,(b),在数组的每个位置,i,(0,i,n,),搜索成功的概率相同，均为,p,/,n,。,1.4.,复杂度的有关概念,例,2,直接插入排序算法,1.5,。,以元素的比较作为基本操作。,最好情况下的时间复杂度：,(,n,),最坏情况下的时间复杂度：,在等概率前提下，平均情况下的时间复杂度：,二、举例,算法分析的基本法则,非递归算法：,（,1,）,for/while,循环,循环体内计算时间*循环次数；,（,2,）嵌套循环,循环体内计算时间*所有循环次数；,（,3,）顺序语句,各语句计算时间相加；,（,4,）,if-else,语句,if,语句计算时间和,else,语句计算时间的较大者。,template,void,insertion_sort(Type,*a,int,n),Type key;/,cost times,for(,int,i=1;i=0&,aj,key)/,c4 sum of,ti,aj+1=,aj,;/,c5 sum of(ti-1),j-;/,c6 sum,og,(ti-1),aj+1=key;/,c7 n-1,在最好情况下，,t,i,=1,for 1,i,n,;,在最坏情况下，,t,i,i,+1,for 1,i,=2),return,F,(,n,-1)+,F,(,n,-2);,解：,该算法的计算时间,T(,n,),满足递归方程：,T(,n,)=T(,n,-1)+T(,n,-2)+1,n,1,；,初始条件,T(0)=T(1)=0,。,1.5.,分析和求解复杂度的方法,例,3,用平摊的办法来统计基本操作的次数（,Amortized Analysis,）,(1.13),整型数组,A(1,：,n,),初始化为,n,个正整数的集合,双链表,List,初始化为仅含一个,元素,0,for,(,j,=1;,j,=,n,;,j,+),x=,A(,j,);,将,x,插入到表,List,尾,if,x,是偶数,then,while,表,List,中,x,的前面元素为奇数,在表,List,中删除,x,的前面的那个元素,end,while,end,if,end for,解：,算法的基本操作为元素的插入和删除操作。算法中插入操作的次数为,n,次，而删除操作的次数最多为,n,-1,次，所以，算法的基本操作最少,n,次，最多,2,n,-1,次。,1.5.,分析和求解复杂度的方法,1,典型的求和公式,0,i,n,f,(,i,),二、求解算法复杂度的基本方法,1.5.,分析和求解复杂度的方法,2.,积分近似求和,如果连续函数,f,(,n,),是单调递减的，则有,如果连续函数,f,(,n,),是单调递增的，则有,1.5.,分析和求解复杂度的方法,1.5.,分析和求解复杂度的方法,1.5.,分析和求解复杂度的方法,1.5.,分析和求解复杂度的方法,递归是一种重要的程序设计方法。有些问题的算法运用递归过程来表示不仅自然简洁，而且也易于验证其正确性。递归算法的特点就是：易读，易写，易证。递归和归纳紧密相关。归纳定义的东西往往易写出其递归的算法；而递归的算法往往可用归纳法来证明。递归算法的时间复杂度分析