计算机算法基础课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,有两种思想,像珠宝商放在天鹅绒上的宝石一样熠熠生辉,.,一个是微积分，另一个就是算法,.,微积分以及在微积分基础上建立起来的数学分析体系造就了现代科学,而算法造就了现代世界,.,David Berlinski,算法的研究内容,问题是否可解,1930s,研究集中于判断特定问题在计算机上是否可解，基本方法为：选定一个计算模型，观察是否能在该模型上创建能解决问题的算法。这些计算模型包括：,Post machines,、,Turing machines,等。这一阶段的成果是：,大部分问题为不可解,。,高效率的解决方法,随着计算机的发展和数据资源的增加，算法研究转向针对可解的问题，找到高效率的解决方法。,算法的应用,数据库中的检索,搜索引擎中的检索,公共密钥加密和数字签名技术,优化问题,最短路径,资源分配,章节安排,计算机算法基础,，余祥宣、崔国华、邹海明著，华中科技大学出版社,第一章 导引与基本数据结构,第二章 分治法,第三章 贪心方法,第四章 动态规划,第五章 检索与周游,第六章 回溯法,第七章 分枝,-,限界,第八章,NP-,问题,预备知识,数学：集合、证明方法（直接、间接、反证、反例、归纳假设）、对数基础、FLOOR&CEILING函数、阶乘、递归关系,数据结构：链接表、图、树、二元树,第一章 导引与基本数据结构,1.1,算法的定义及特性,什么是算法？,一系列将问题的输入转换为输出的计算或操作步骤,。,2.,算法的五个重要特性,确定性,、,能行性,、,输入,、,输出,、,有穷性,1,）,确定性,：算法的每种运算必须要有确切的定义，不能有二义性。,例：不符合确定性的运算,5/0,将,6,或,7,与,x,相加,未赋值变量参与运算,2,）,能行性,算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。,例：整数的算术运算是“能行”的,实数的算术运算是,“不能行”,的,3,）,输入,每个算法有,0,个或,多,个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合,定义域,（或值域）,4,）,输出,一个算法产生,一个,或,多个,输出，这些输出是同输入有某种特定关系的量。,5,）,有穷性,一个算法总是在执行了,有穷步,的运算之后,终止,。,计算过程,：只满足确定性、能行性、输入、输出四个特性但,不一定能终止,的一组规则。,准确理解算法和计算过程的区别：,不能终止的计算过程：操作系统,算法是“可以终止的计算过程”,算法的时效性：只能把在,相当,有穷步内终止的算法投,入到计算机上运行,3.,我们的主要任务,算法学习将涉及,5,个方面的内容：,1,）,设计算法,：创造性的活动,2,）,表示算法,：思想的表示形式,3,）,确认算法,：证明算法的正确性,程序的证明,4,）,分析算法,：算法时空特性分析,5,）,测试程序,：调试和作出时空分布图,本课程集中于学习算法的,设计,与,分析,。通过学习，掌握计算机算法设计和分析,基本策略与方法,，为设计更复杂、更有效的算法奠定基础,4.,算法描述语言,自然语言,数学语言,流程图,程序设计语言等等,.,5.,问题的求解过程,2),建立数学模型,1),问题的陈述,3),算法设计,用科学规范的语言,对所求解的问题做准确的描述,.,通过对问题的分析,找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述,.,根据数学模型设计问题的计算机求解算法,.,4),算法的正确性证明,5),算法的程序实现,6),算法分析,证明算法对一切合法输入均能在有限次计算后产生正确输出,.,对执行该算法所消耗的计算机资源进行估算,.,将算法正确地编写成机器语言程序,.,1.2,分析算法,1.,分析算法的目的,在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。,算法分析是计算机领域的古老而前沿的课题。,进行算法分析的基本技术：抽象,2.,重要的假设和约定,1,）计算机模型的假设,Turing,机模型：计算机形式理论模型,通用计算机模型：,单处理器,有足够的“内存”,能在固定的时间内存取数据单元,2,）计算的约定,确定使用什么样的运算及其执行时间。,从计算时间上，运算的分类：,时间囿界于常数的运算,：尽管每种运算的执行时间不同，但一般只花 一个,固定量,的时间（单位时间）就可完成。,基本算术运算，如整数、浮点数的加、减、乘、除,字符运算,赋值,运算,过程调用等,2,）计算的约定（续）,其他运算,：,字符串操作：与字符串中字符的数量成正比,记录操作：与记录的属性数、属性类型等有关,特点：运算时间,无定量,如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。,如：,T,string,= Length,（,String,）*,t,char,算法的执行时间,=,F,i,*t,i,其中，,F,i,是算法中用到的某种运算,i,的次数，,t,i,是该运算执行一次所用的时间。,3,）工作数据集的选择,编制能够反映算法在最好、平均、最坏情况下工作的,数据配置,。然后使用这些数据配置运行算法，以了解算法的性能。,测试数据集的生成,作为算法分析的数据集：典型特征,作为程序性能测试的数据集：对执行指标产生影响的性质,3. 如何进行算法分析？,对算法进行全面分析，可分两个阶段进行：,事前分析,：就算法本身，通过对其执行性能的理论分析，,得出关于算法特性,时间和空间,的一个特征,函数（,、,）,与计算机物理软硬件没有,直接关系。,事后测试,：将算法编制成程序后实际放到计算机上运行，,收集其执行时间和空间占用等统计资料，进行,分析判断直接与物理实现有关。,1,）事前分析,目的：试图得出关于算法执行特性的一种形式描,述，以“理论上”衡量算法的“好坏”。,如何给出反映算法执行特性的描述,？,最直接方法：,统计算法中各种运算的执行情况，包括：,运用了哪些运算,每种运算被执行的次数,该种运算执行一次所花费的时间等。,算法的执行时间,=,F,i,*,t,i,频率计数,例：,x,x+y for i 1 to n do for i 1 to n do,x x + y for j 1 to n do,repeat x x +y,repeat,repeat,(a) (b) (c),分析：,(a),：,x,x+y,执行了,1,次,(b),：,x,x+y,执行了,n,次,(c),：,x,x+y,执行了,n,2,次,定义：,频率计数,：一条,语句,或一种,运算,在算法（或程序）体中的执行次数。,算法,2.7,插入分类,procedure INSERTIONSORT(A,n),/,将,A(1,：,n),中的元素按非降次序分类，,n1/,1 A(0)-/,设置初始边界值,2 for j2 to n do /A(1:j-1),已分类,/,3 itemA(j);ij-1,4 while itemA(i) do /0ij/,5 A(i+1)A(i); ii-1,6 repeat,7 A(i+1) item;,8 repeat,end INSERTIONSORT,(8, 5, 4, 9),(,8,5, 4, 9),(,5, 8, 4, 9),(,5, 8,4, 9),(,4,5,8,9,),(,4, 5, 8, 9,),一条语句在整个程序运行时实际执行时间,=,频率计数,*,每执行一次该语句所需的时间,如何刻画算法执行特性的形式描述,实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，没有统一的描述模型。,在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。,数量级,语句的数量级,：语句的执行频率,例：,1,，,n,，,n,2,算法的数量级,：算法所包含的所有语句的执,行频率之和。,算法的数量级从本质上反映了一个算法的执行特性。,例：假如求解同一个问题的三个算法分别具有,n,，,n,2,，,n,3,数,量级。,若,n=10,，则可能的执行时间将分别是,10,，,100,，,1000,个单,位时间,与环境因素无关。,计算时间,/,频率计数的表示函数,通过事前分析给出算法计算时间（频率计数）的一个,函数,表示形式，一般记为与,输入规模,n,有关的函数形式：,f(n),注：最高次项与函数整体的关系,空间特性分析（略）,2,）事后测试,目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论,包括正确性、执行性能等，比较、优化所设计的算法。,分析手段：作时、空性能分布图,4.,计算时间的渐近表示,记：算法的计算时间为f(n),数量级限界函数为g(n),其中，,n是输入或输出规模的某种测度。,f(n)表示算法的“实际”执行时间,与机器及语言有关,。,g(n)是,形式简单,的函数，如n,m,，logn，2,n,，n!等。是事前分析中通过对计算时间或频率计数统计分析所得的、,与机器及语言无关,的函数。,以下给出算法执行时间：,上界,（,）、,下界,（,）、,“平均”,（ ）的定义。,1,）上界函数,定义1 如果存在两个正常数c和n,0,，对于所有的n,n,0,，有,|f(n)| c|g(n)|,则记作,f(n) =,(g(n),含义：,如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个,上界函数,。,f(n)的数量级就是g(n)。,试图求出,最小,的g(n)，使得f(n) =,(g(n)。,多项式定理:,定理1 若A(n) = a,m,n,m,+,+a,1,n+a,0,是一个m次多项,式，则有A(n) =,(,n,m,),即：变量n的固定阶数为m的任一多项式，与此多,项式的最高阶,n,m,同阶。,证明：取,n,0,=1,当nn,0,时，有,|A(n)|a,m,|n,m,+|a,1,|n+|a,0,|,(|a,m,|+|a,m-1,|/n+|a,0,|/n,m,) n,m,(|a,m,|+|a,m-1,|+|a,0,|) n,m,令c= |a,m,|+|a,m-1,|+|a,0,|,则，定理得证。,计算时间的数量级对算法有效性的影响,数量级,的大小对算法的有效性有,决定性,的影响。,例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n,2,和nlogn。则，,n=1024：分别需要,1048576,和,10240,次运算。,n=2048：分别需要,4194304,和,22528,次运算。,分析：在n加倍的情况下，一个,(n,2,)的算法计算时间增长,4,倍，而一个,(nlogn)算法则只用,两,倍多一点的时间即,可完成。,算法,2.8,归并分类,procedure MERGESORT(low,high),/A(low:high),是一个全程数组，它含有,high-low+1,0,个待分类的元素,/,integer low,high,if lowhigh then,mid,/,计算,中分点,/,call,MERGESORT,(low,mid),/,在第一个子集合上分类,(,递归,)/,call,MERGESORT,(mid+1,high),/,在第二个子集合上分类,(,递归,)/,call,MERGE,(low,mid,high),/,归并已分类的两子集合,/,endif,end MERGESORT,Merge,算法示例,(4, 5, 8, 9),|,(1, 2, 6, 7),(1, 2, 4, 5, 6, 7, 8, 9),参数：,low = 1; high = 8; mid = 4,(4, 5, 8, 9),|,( 1, 2, 6, 7),h,j,j,j,j,h,h,(1,4,2,5,6,7,8,9),j,算法分类（计算时间）,多项式时间算法：可用多项式（函数）对其计算时间限界的算法。,常见的多项式限界函数有：,(1) ,(logn) ,(n) ,(nlogn) ,(n,2,) ,(n,3,),指数时间算法：计算时间用指数函数限界的算法,常见的指数时间限界函数：,(2,n,) ,(n！) 0,。,特殊形态的二元树,满二元树,：深度为,k,且有,2,k,-1,个结点的二元树,完全二元树,：一棵有,n,个结点深度为,k,的二元树，当它的结点相当于深度为,k,的满二元树中编号为,1,到,n,的结点时，称该二元树是完全的。,完全二元树的叶子结点至多出现在相邻的两级上。,完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理,1.2,）。,二元树的表示方法,1.,数组表示法：对于完全二元树，空间效率好；其他二元树，要浪费大量空间,2.,链表法：结构简单，有效。链表中每个结点有三个信息段，,LCHILD,DATA,和,RCHILD,堆,：堆是一棵完全二元树，它的每个结点的值至少和该结点的儿子们（如果存在的话）的值一样大（,max-,堆）（或小，,min-,堆）。,二分检索树,：二分检索树是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：,的左子树的所有元素比根结点中的元素小；,的右子树的所有元素比根结点中的元素大；,的左子树和右子树也是二分检索树。,注：二分检索树要求树中所有结点的元素值互异,3.,树的应用,不相交集合的合并及搜索问题,问题描述：,给定一个全集,U,，该集合包含,n,个元素,很明显该集合包含多个,不相交的子集,某些应用需要实现这些,不相交子集的合并,、,查找,操作，并且这些操作最终可形成,序列,如何高效率实现这些操作序列就是我们要解决的问题,集合操作举例,n=10，U=1, 2, 3, 4, 5, 6, 7, 8, 9, 10,s1=1, 7, 8, 9; s2=2, 5, 10; s3=3, 4, 6,合并运算： s1s2=1, 7, 8, 9, 2, 5, 10,查找运算： 元素4包含在s1, s2, s3的哪个集合中？,方法一位向量,方法一：位向量,s1= 1, 0, 0, 0, 0, 0, 1, 1, 1, 0；,s2= 0, 1, 0, 0, 1, 0, 0, 0, 0, 1；,利用位运算可得出,s1s2= 1, 1, 0, 0, 1, 0, 1, 1, 1, 1,缺点：n很大，超过一个机器字长，而参与运算的集合的势很小时，运算与n成正比。,方法二集合元素表,s1=1, 7, 8, 9;,s2=2, 5, 10,合并操作：| s1|+| s2|,查找操作：最坏为|n|,方法三树,数据结构,字符数组,U=1, 2, 3, 4, 5, 6, 7, 8, 9, 10,子集,s1=1, 7, 8, 9; s2=2, 5, 10,则用数组,Parent,表示集合,s1,和,s2,：数组中记录的是节点,Ui,的父节点在,Parent,中的位置,（,1,）,（,2,）,（,3,）,（,4,）,（,5,）,（,6,）,（,7,）,（,8,）,（,9,）,（,10,）,0,0,2,1,1,1,2,合并操作,U(1,2),后：（,Parent1=2,）,（,1,）,（,2,）,（,3,）,（,4,）,（,5,）,（,6,）,（,7,）,（,8,）,（,9,）,（,10,）,2,0,2,1,1,1,2,查找元素F(9),U,操作为常量时间，,F,操作则与查找元素在集合树中的层数有关。,U和F的性能问题退化树,问题描述：有集合如下：,（1）（2）（n）,0 0 0,依次作下列操作：U(1,2), F(1), U(2,3), F(1), , U(n-1,n),按照算法U和F，最终得到的树及时间耗费分析,U：每次都是常量时间，因此总共是O(n-1),F(1)：2+3+(n-1)，因此是O(n2),症结？合并操作！,加权规则,节点数少的树合并到节点数多的树中。,字符数组,U=1, 2, 3, 4, 5, 6, 7, 8, 9, 10,子集,s1=1, 7, 8, 9; s2=2, 5, 10,（,1,）,（,2,）,（,3,）,（,4,）,（,5,）,（,6,）,（,7,）,（,8,）,（,9,）,（,10,）,-4,-3,2,1,1,1,2,Union F序列演示,分析,Union(1,2), F(1), Union (2,3), F(1), , Union (n-1,n),Union合并的开销较u要大，但仍然是常量时间,每次查找1耗费时间为2，常量时间，则执行n-2次查找耗费时间为O(n),注意：本例的查找耗时不是最坏情况,最坏情况由引理1.3给出,引理1.3,引理,1.3,设,T,是一棵由算法,union,所产生的有,n,个节点的树。在,T,中没有节点的级数会大于（,logn,的下界,+1,）,证明：,n=1,，显然引理为真；,i,为,T,的级数，假设当,i=n-1,时，引理为真，现证对于,i=n,，引理也为真；,令,k,和,j,是形成树,T,的最后一次合并，即,Union(k,j),；,用,count(),表示数的节点数，假设,count(j)=m,，那么,count(k)=n-m,；,不失一般性，可假设,1=mn/2,，则有,m=n-m,；,那么经,Union,合并后，,j,的父亲为,k,；如右图：,则,T,的级数：,1,）等于,k,的级数：,log(n-m),的下界,+1=,（,logn,的下界,+1,）,2,）或者等于（,j,的级数,+1,）：（,logm,的下界,+2,）,=,（,log(n/2),的下界,+2,）,=n），处理时间接近O(m)，但稍差。详细描述见引理1.4。,例1.2,4.,图,图,由称之为结点和边的两个集合组成，记为,G=,（,V,，,E,）。其中，是一个有限非空的结点集合；是结点对偶的集合，的每一对偶表示的一条边。,有关图的的重要概念,无向图,：边的表示（，）,有向图,：边的表示,，,成本,：带有成本的图称为网络,邻接,：,结点的度（出度入度,）,路径,：由结点,v,p,到,v,q,的一条路（,path,）是结点,v,p,，,v,i1,，,v,i2,，,，,v,im,，,v,q,的一个序,列，它使得,( v,p,，,v,i1,),，,( v,i1,，,v,i2,),，,，,(,v,im,，,v,q,),是,E,（,G,）的边。,路的长度,：组成路的边数。,简单路径,：除了第一和最后一个结点可以相同以外，,其它所有结点都不同。,环,：第一个和最后一个结点相同的简单路。,连通图,：在无向图中，如果每对结点之间都存在一条,路，则称该图是连通的。,子图,：是由,G,的结点集,V,的子集（记为,VB,）和边集,E,中连接,VB,中结点的边的子集所组成的图。,连通分图,：一个图的最大连通子图。,有向图的强连通性,：在有向图中，如果对于每一对结,点,i,和,j,，既存在一条从,i,到,j,的路，又存在一条从,j,到,i,的路，则称该有向图是强连通的。,图的表示方法,邻接矩阵 邻接表,1.5,递归和消去递归,1.,递归,直接调用自己或间接通过一些语句调用自己,递归是一种强有力的设计方法,描述某些数学问题非常自然，易于证明算法,递归的效率问题,执行时间、空间消耗多,例,1.3,斐波那契,(Fibonacci),序列：,F,0,= F,1,= 1,F,i,= F,i-1,+ F,i-2,（,i1),算法,1.7,求斐波那契数,procedure F(n),/,返回第,n,个斐波那契数,/,integer n,if nb /,if b=0 then return(a),else return (GCD(b,a mod b),endif,end GCD,例：,GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;,GCD(22,8),GCD(8,6),GCD(6,2),GCD(2,0),2,递推,递,推,递,推,递,推,回,归,回,归,回,归,回归,结果为,GCD(22,8)=2,例,1.5,递归在,非数值算法,设计中的应用,已知元素,x,，判断,x,是否在,A,（,1,：,n,）中。,算法,1.9,在,A,（,1,：,n,）中检索,x,procedure SEARCH(i),/,如果在,A,（,1,：,n,）中有一元素,A,（,k,）,=x,，则将其第一次出现的下标,k,返回，否则返回,0/,global n,x,A(1:n),case,:in: return(0),:A(i) = x; return(i),:else: return(SEARCH(i+1),endcase,end SEARCH,2.,消去递归,直接递归的消去规则,：,基本思路,：将递归过程中出现递归调用的地方，用等价的,非递归代码,来代替，并对,return,语句,做适当处理。,13,条规则：,处理直接递归调用中的递归代码和,return,语句，将之转换成等价的迭代代码。,初始化, 在过程的开始部分，插入说明为栈的代码并将其初始化为空。在一般情况下，这个栈用来存放参数、局部变量和函数的值、每次递归调用的返回地址。, 将标号,L,1,附于第一条可执行语句。然后对于每一处递归调用都用一组执行下列规则的指令来代替。,处理递归调用语句, 将所有参数和局部变量的值存入栈。,栈顶指针,可作为一个全程变量来看待。, 建立第,i,个新标号,L,i,，并将,i,存入栈。这个标号的,i,值将用来计算返回地址。,此标号放在规则所描述的程序段中。, 计算这次调用的各实在参数（可能是表达式）的值，并把这些值赋给相应的形式参数。, 插入一条无条件转向语句转向过程的开始部分：,Goto L,1,对递归嵌套调用的处理, 如果这过程是函数，则对递归过程中含有此次函数调用的那条语句做如下处理：将该语句的此次函数调用部分用从栈顶取回该函数值的代码来代替，其余部分的代码按原描述方式照抄，并将中建立的标号附于这条语句上。,如果此过程不是函数，则将中建立的标号附于所产生的转移语句后面的那条语句。,以上步骤实现消去过程中的递归调用。下面对过程中出现,return语句,进行处理（纯过程结束处的end可看成是一条没有值与之联系的return语句）。,对每个有,return,语句的地方，执行下述规则,：, 如果栈为,空,，则执行,正常返回,。, 否则，将所有输出参数（带有返回值的出口参数，,out/inout,型）的当前值赋给栈顶上的那些对应的变量。, 如果栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。, 从栈中退出所有局部变量和参数的值并吧它们赋给对应的变量。, 如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在,return,后面的表达式并将结果值存入栈顶。, 用返回地址标号的下标实现对该标号的转向。,例,1.6,递归调用示例,求数组元素中的最大值,算法,1.10,递归求取数组元素的最大值,procedure MAX1(i),/,查找数组,A,中最大值元素，并返回该元素的最大下标。,/,global integer n,A(1:n),j,k,integer i,if i A(j) then ki,else kj,endif,else kn,endif,return(k),/,递归调用的返回,/,end MAX1,消去上例中的递归,算法,1.11,使用上述的规则消去例,1.10,中的递归代码,procedure MAX2(i),local integer j,k; global integer n, A(1:n),integer I,integer,STACK,(1:2*n),top,0,/,规则,1,，声明栈的代码，并初始化为空,/,L1:,if i A(j) then k I,else k j,endif,else k n,endif,if top = 0 then,return(k),/,规则,8,， 如果栈空，则正常返回,/,else,addr,STACK(top);top top-1;,/,规则,10,， 从,栈中退出返回标号,/,i,STACK(top);top top-1;,/,规则,11,， 从栈中退,出局部变量和参数的值,/,top top+1;STACK(top) ,k,;,/,规则,12,， 计算返,回值，并将之入栈,/,if addr = 2 then,goto L2,endif,/,规则,13,， 用返回,地址标号的下标实现对该标号的转向,/,endif,end MAX2,进一步优化和简化经过消去递归产生的迭代程序。,算法,1.12,算法,1.11,的改进模型,procedure MAX3(A,n),integer i,k,n;,i,k n,while i1 do,i,i-1,if A(i) A(k) then k,i endif,repeat,return(k),end MAX3,不必死套,13,条规则，应具体情况具体分析,procedure GCD1(a,b) /,约定,ab /,L1: if b=0 then return(a),else t,b;b a mod b;a t;go to L1,endif,end GCD1,整理后得,：,procedure GCD2(a,b),while b,0 do,t,b;b a mod b;a t,repeat,return(a),end GCD2,渐进分析,时间复杂性渐进阶分析的规则:,(最坏情况),1). 赋值,比较,算术运算,逻辑运算,读写单个变量(常量)只需1单位时间,2). 执行条件语句,if,c,then,S1,else,S2 的时间为,T,C,+max(T,S1,T,S2,).,3). 选择语句,case,A,of,a1,:,s1；a2,:,s2；,.；,am,:,sm,需要的时间为,max（T,S1,T,S2,., T,Sm,）.,4). 访问数组的单个分量或纪录的单个域需要,一个单位时间,.,5). 执行,for,循环语句的时间=,执行循环体时间*循环次数.,6).,while,c,do,s,(,repeat,s,until,c,),语句时间=,(T,c,+T,s,)*循环次数.,7). 用,goto,从循环体内跳到循环体末或循环后面的语句时,不需额外时间,8). 过程或函数调用语句,对非递归调用,根据调用层次由里向外用规则1-7进行分析；,对递归调用,可建立关于,T(n)的,递归方程,求解该方程得到,T(n),.,例 题,1-1,算法1-2:二分查找 (假定c是A的最后一元),例 题,1-1,分析,:,问题规模为,n,元运算执行时间设为赋值,a,判断,t,加法,s,除法,d,减法,b.,最坏情况,T,max,(n) = 6a+4t+2s+d+(2a+2s+3t+d),logn,function b-search(c), L:=1; U:=n; 2,found:=false; 1,while not found and U=L do 3, i:=(L+U)div2; 3,if c=Ai 1,then found:=true,1,else if cAi 1,then L:=i+1,1,else U:=i-1,if found,then b-search:=i,else b-search:=0 1,Logn+1,算法设计与分析,已知不重复且从小到大排列的m个整数的数组A1.m,m=2,K,K为正整数.对于给定的整数c,要求找到一个下标i,使得Ai=c.找不到返回0.,例 题,1-1,function b-search(c,L,U), if Uc then 1,b-search:= b-search(c,L, index-1); 3+T(m/2),else,b-search:= b-search(c,index+1,U); 3+T(m/2),; ,设,T(m),是,b-search,在最坏情况下的时间复杂性,则,T(m),满足如下递归方程,:,2,m=,0,13,m=1,11+T(,m,/2),m1,T(m)=,解得,: T(m) =11logm+13=,(logm),算法1-3:二分查找递归算法,求Fibonacci数列的前N项,a,0, a,1, a,N,其中,a,0,=,0, a,1,=,1,a,i,= a,i-1,+,a,i-2,算法1-4,Procedure seq(n),function A(n), if n=0 then 1,A:=0 1,else if n=1 then 1,A:=1 1,else A:=A(n-1)+A(n-2) 6+F(n-1)+F(n-2),;, if n1,F(n)=,例 题,1-2,4).套用公式法,若递归方程形如:,T(n)=,a,T(,n/b,)+,f,(,n,),可根据,f,(,n,),的不同情况套用公式,1),若,0,使得,f,(,n,)=O(n,log,b,a,-,),则T(n)=,(,n,log,b,a,),2),若,f,(,n,)=,(n,log,b,a,), 则T(,n,)=,(,n,log,b,a,log,n,),3),若,0,使得,f,(,n,)=,(n,log,b,a,+,),且,c, 1,f,(,n,),是渐近的正函数,主定理：比较,f,(,n,),和,n,log,b,a,:,f,(,n,) =,O,(,n,log,b,a,),常数, 0.,T,(,n,) = (,n,log,b,a,),f,(,n,) = (,n,log,b,a,lg,k,n,),常数,k, 0.,T,(,n,) = (,n,log,b,a,lg,k,+1,n,),f,(,n,) =,O,(,n,log,b,a,+,),常数, 0.,T,(,n,) = (,f,(,n,),主方法例子,T(n)=9T(n/3)+n,T(n)=T(2n/3)+1,T(n)=2T(n/2)+nlgn,