计算机算法基础课件

《计算机算法基础课件》由会员分享，可在线阅读，更多相关《计算机算法基础课件（102页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,有两种思想,,,像珠宝商放在天鹅绒上的宝石一样熠熠生辉,.,一个是微积分，另一个就是算法,.,微积分以及在微积分基础上建立起来的数学分析体系造就了现代科学,,,而算法造就了现代世界,.,,,——David Berlinski,,算法的研究内容,,问题是否可解,,1930’s,研究集中于判断特定问题在计算机上是否可解，基本方法为：选定一个计算模型，观察是否能在该模型上创建能解决问题的算法。这些计算模型包括：,Post machines,、,Turing machines,等。这一阶段的成果是：,

2、大部分问题为不可解,。,,高效率的解决方法,,随着计算机的发展和数据资源的增加，算法研究转向针对可解的问题，找到高效率的解决方法。,,算法的应用,,数据库中的检索,,搜索引擎中的检索,,公共密钥加密和数字签名技术,,优化问题,,最短路径,,资源分配,,…,,章节安排,,《,计算机算法基础,》,，余祥宣、崔国华、邹海明著，华中科技大学出版社,,,第一章 导引与基本数据结构,√,,第二章 分治法,√,,第三章 贪心方法,√,,第四章 动态规划,√,,第五章 检索与周游,√,,第六章 回溯法,√,,第七章 分枝,-,限界,√,,第八章,NP-,问题,⊙,,,,预备知识,,数学：集合、证明方法（直接、

3、间接、反证、反例、归纳假设）、对数基础、FLOOR&CEILING函数、阶乘、递归关系,,数据结构：链接表、图、树、二元树,,第一章 导引与基本数据结构,,1.1,算法的定义及特性,,,什么是算法？,,,一系列将问题的输入转换为输出的计算或操作步骤,。,,,,2.,算法的五个重要特性,,确定性,、,能行性,、,输入,、,输出,、,有穷性,1,）,确定性,：算法的每种运算必须要有确切的定义，不能有二义性。,,例：不符合确定性的运算,,,5/0,,,将,6,或,7,与,x,相加,,未赋值变量参与运算,,2,）,能行性,,算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时

4、间内完成。,,例：整数的算术运算是“能行”的,,实数的算术运算是,“不能行”,的,,,3,）,输入,,每个算法有,0,个或,多,个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合,——,定义域,（或值域）,,4,）,输出,,一个算法产生,一个,或,多个,输出，这些输出是同输入有某种特定关系的量。,,5,）,有穷性,,一个算法总是在执行了,有穷步,的运算之后,终止,。,,,,计算过程,：只满足确定性、能行性、输入、输出四个特性但,不一定能终止,的一组规则。,,,,准确理解算法和计算过程的区别：,,不能终止的计算过程：操作系统,,算法是“可以终止的计算过程”,,算法的时效性：只能把在,

5、相当,有穷步内终止的算法投,,入到计算机上运行,,3.,我们的主要任务,,算法学习将涉及,5,个方面的内容：,,,1,）,设计算法,：创造性的活动,,,2,）,表示算法,：思想的表示形式,,,3,）,确认算法,：证明算法的正确性,,程序的证明,,,4,）,分析算法,：算法时空特性分析,,,5,）,测试程序,：调试和作出时空分布图,,本课程集中于学习算法的,设计,与,分析,。通过学习，掌握计算机算法设计和分析,基本策略与方法,，为设计更复杂、更有效的算法奠定基础,,4.,算法描述语言,自然语言,,,数学语言,,,流程图,,,程序设计语言等等,.,5.,问题的求解过程,2),建立数学模型,1),问

6、题的陈述,3),算法设计,用科学规范的语言,,,对所求解的问题做准确的描述,.,通过对问题的分析,,,找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述,.,根据数学模型设计问题的计算机求解算法,.,,4),算法的正确性证明,5),算法的程序实现,6),算法分析,证明算法对一切合法输入均能在有限次计算后产生正确输出,.,对执行该算法所消耗的计算机资源进行估算,.,将算法正确地编写成机器语言程序,.,,1.2,分析算法,1.,分析算法的目的,,在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物

7、力浪费。,,,算法分析是计算机领域的古老而前沿的课题。,,,进行算法分析的基本技术：抽象,,2.,重要的假设和约定,,,1,）计算机模型的假设,,,Turing,机模型：计算机形式理论模型,,通用计算机模型：,,单处理器,,有足够的“内存”,,能在固定的时间内存取数据单元,,,2,）计算的约定,,,确定使用什么样的运算及其执行时间。,,从计算时间上，运算的分类：,,,时间囿界于常数的运算,：尽管每种运算的执行时间不同，但一般只花 一个,固定量,的时间（单位时间）就可完成。,,,·,基本算术运算，如整数、浮点数的加、减、乘、除,,,·,字符运算,,,·,赋值,运算,,,·,过程调用等,,2,）计

8、算的约定（续）,其他运算,：,,,·,字符串操作：与字符串中字符的数量成正比,,,·,记录操作：与记录的属性数、属性类型等有关,,,·,,特点：运算时间,无定量,,,如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。,,,,如：,T,string,= Length,（,String,）*,t,char,,,算法的执行时间,=,∑F,i,*t,i,,其中，,F,i,是算法中用到的某种运算,i,的次数，,t,i,是该运算执行一次所用的时间。,,,3,）工作数据集的选择,,,编制能够反映算法在最好、平均、最坏情况下工作的,数据配置,。然后使用这些数据配置运行算法，以了解算法的性能。,,

9、测试数据集的生成,,作为算法分析的数据集：典型特征,,作为程序性能测试的数据集：对执行指标产生影响的性质,,3. 如何进行算法分析？,,对算法进行全面分析，可分两个阶段进行：,,,事前分析,：就算法本身，通过对其执行性能的理论分析，,,得出关于算法特性——,时间和空间,的一个特征,,函数（,Ο,、,Ω,）,——与计算机物理软硬件没有,,直接关系。,,事后测试,：将算法编制成程序后实际放到计算机上运行，,,收集其执行时间和空间占用等统计资料，进行,,分析判断——直接与物理实现有关。,,1,）事前分析,,目的：试图得出关于算法执行特性的一种形式描,,述，以“理论上”衡量算法的“好坏”。,,,如何给

10、出反映算法执行特性的描述,？,,最直接方法：,统计算法中各种运算的执行情况，包括：,,运用了哪些运算,,每种运算被执行的次数,,该种运算执行一次所花费的时间等。,,,算法的执行时间,=,∑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)

11、 (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),中的元素按非降次序分类，,n≥1//,,1 A(0)←-∞//,设置初始边界值,,,2 for j←2 to n do //A(1:j-1),已分类,//,,3

12、 item←A(j);i←j-1,,4 while item

13、一次该语句所需的时间,,,如何刻画算法执行特性的形式描述,,实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，没有统一的描述模型。,,在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。,,数量级,,,语句的数量级,：语句的执行频率,,例：,1,，,n,，,n,2,,,算法的数量级,：算法所包含的所有语句的执,,行频率之和。,,,算法的数量级从本质上反映了一个算法的执行特性。,,例：假如求解同一个问题的三个算法分别具有,n,，,n,2,,，,n,3,数,,量级。,,若,n=10,，则可能的执行时间将分别是,10,，,100,，,1000,

14、个单,,位时间,——,与环境因素无关。,,计算时间,/,频率计数的表示函数,,通过事前分析给出算法计算时间（频率计数）的一个,函数,表示形式，一般记为与,输入规模,n,有关的函数形式：,f(n),,,注：最高次项与函数整体的关系,,,空间特性分析（略）,,2,）事后测试,,目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论,——,包括正确性、执行性能等，比较、优化所设计的算法。,,分析手段：作时、空性能分布图,,4.,计算时间的渐近表示,记：算法的计算时间为f(n),,数量级限界函数为g(n),,其中，,,n是输入或输出规模的某种测度。,,f(n)表示算法的“实际”执行时间—,与

15、机器及语言有关,。,,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)的一个,上界函数,。

16、,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,当n≥n,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

17、,,,令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,归并分类,,,,,p

18、rocedure MERGESORT(low,high),,//A(low:high),是一个全程数组，它含有,high-low+1,≥0,个待分类的元素,//,,integer low,high,,if low

19、SORT,,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,),,指数时间算法：计算

20、时间用指数函数限界的算法,,常见的指数时间限界函数：,,,Ο,(2,n,) <,Ο,(n！) <,Ο,(n,n,),,,说明：当n取值较大时，指数时间算法和多项式时间,,算法在计算时间上非常悬殊。,,典型的计算时间函数曲线,,当数据集的规模很大时，要在现有的计算机系统上运行具有比,Ο,(nlogn),复杂度还高的算法是比较困难的。,,,指数时间算法只有在n取值,非常小时,才实用。,,,要想在顺序处理机上扩大所处理问题的规模，有效的途径是,降低算法的计算复杂度,，而不是（仅仅依靠）提高计算机的速度。,,计算时间函数值比较,,定义1.2 如果存在两个正常数c和n,0,，对于所有的n,≥n,0,，

21、,,有,,|f(n)| ≥ c|g(n)|,,则记作,f(n) =,Ω,(g(n)),,,含义：,,如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个下,界函数,。,,试图求出“,最大,”的g(n)，使得f(n) =,Ω,(g(n))。,2,）下界函数,,定义1.3 如果存在正常数,c,1,，,c,2,和n,0,，对于所有的n,≥n,0,，有,,c,1,|g(n)| ≤|f(n)| ≤ c,2,|g(n)|,,则记作,,,含义：,,算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作：,,既

22、有,f(n) =,Ω,(g(n))，又有f(n) =,Ο,(g(n)),,3,）“平均情况”限界函数,,4,）限界函数的性质,1）若 且 ，则 。即,О,具有传递性。（ 同）,,2） 当且仅当,,3）若 ，则 。即， 定义了一个等价关系（等价类）,,5.,常用的整数求和公式,在算法分析中，在统计语句的频率时，求和公式的一般表示形式为：,,,,,,如：,,1+1+…+1,（有,n,项,1,）,= n,,1+2+

23、…+n = n,2,,1,2,+ 2,2,+…+ n,2,= n,3,,2,0,+ 2,1,+…+ 2,n,= 2,n+1,,,1.3,关于,SPARKS,语言,本书为描述算法选用的一种类计算机语言,,类PASCAL语言,,结构化程序描述,,,1.,基本语法成分,1,）数据类型：整型、实型、布尔型、字符型,,2,）变量声明：,integer i,j; boolean b; char c,,3,）赋值运算：,（变量）←（表达式）,,4,）逻辑运算：,and or not,,5,）关系运算：＜ ≤ ＝ ≠ ≥ ＞,,6,）变量声明：类型说明符 变量；,,7

24、,）数组声明：,integer A,（,1,：,5,，,7,：,20,）,,,8,）控制结构：,,,顺序,:,,,分支,:,,,·,if condition then S1,,else S2,,endif,,,·,case,,:cond1:S1;,,:cond2:S2;,,…,,:condn:Sn,,:else:Sn+1,,endcase,循环,:,,,·,while cond do,,S,,repeat,,,·,loop,,S,,until cond repeat,,,·,for vble←start to finish by increment do,,S,,repeat,,,,2.,

25、同质异项,,3.,其它,,,函数的定义与调用、函数和过程、变量与形式参数,,1.4,基本数据结构,1.,栈和队列,,栈和队列：,n,个元素的线性表,,利用动态数据结构,——,链表,实现栈或队列,,利用静态数据结构,——,数组,实现栈或队列,,基于以上两种表示形式的栈和队列上的基本运算,,,队列的数组表示,,,栈的数组表示,,用一维数组,STACKS,（,1:n,）表示,,栈底：,STACKS,（,1,） 第,i,个元素,STACKS(i),,栈顶指针：,top,,,procedure ADD(item,STACAK,n,top),,if top,≥,n then call STACKFULL

26、 endif,,top,←,top +1,,STACK(top),←,item,,end add,procedure DELETE(item,STACK,top),,if top,≤ 0 then call STACKEMPTY,,endif,,item ←,STACK(top),,top,←,top-1,,end DELETE,,栈的数组表示——增加、删除,,,栈的链接表表示,,一种单向链接表,,两个信息段：,DATA,存放数据，,LINK,指向前一节点,节点插入,,,call GETNODE(T),,DATA(T),←item,,LINK(T) ←STACK,,STACK ← T,节点删除

27、,,,item,←DATA(STACK),,T ←STACK,,STACK ←LINK(SATCK),,call RETNODE(T),,A,STACK,0,,栈的链接表表示——增加、删除,,,2.,树,,1,）树的一般定义,,定义,1.4,树（,tree,）,是一个或多个结点的,有限,集,,合，它使得：,,有一个指定为,根,（,root,）的结点,,剩余结点被划分成,m,≥0,个不相交的集合：,,,T,1,，,…,，,T,m,,,这些集合的每一个又都是一棵树，并称,T,1,，,…,，,T,m,为根的子树。,,关于树的重要概念,,,结点的度,（,degree,）：一个结点的子树数,,树的度,：

28、树中结点度的最大值,,结点的级,（,level,）（又叫层）：设根是,1,级，若某结点在,p,级，则它的儿子在,p+1,级,,树的高度（或深度）,：树中结点的最大级数,,叶子（终端结点）,：度为,0,的结点,,内结点（非终端结点）,：度不为,0,的结点,,森林,：,m,≥0,个不相交树的集合。,,树的表示方法,,用,链接表,表示 每个结点三个信息段：,TAG,DATA,LINK TAG,＝,0,，,DATA,存数据；,TAG=1,DATA,存链接信息，指向一棵子树,,2,）二元树,,定义,1.5,二元树,（,binary tree,）是结点的有限集合，它或者为,空,，或者由一个根和两棵称为

29、左子树和右子树的不相交二元树所组成。,,,二元树与度为,2,的树的区别,,,二元树性质,1,：,,引理,1.1,一棵二元树第,i,级的最大结点数是,2,i-1,。深度为,k,的二元树的最大结点数为,2,k,-1,,k>0,。,,,,特殊形态的二元树,,,满二元树,：深度为,k,且有,2,k,-1,个结点的二元树,,,,完全二元树,：一棵有,n,个结点深度为,k,的二元树，当它的结点相当于深度为,k,的满二元树中编号为,1,到,n,的结点时，称该二元树是完全的。,,,完全二元树的叶子结点至多出现在相邻的两级上。,,完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理,1.2,）。,,,二元

30、树的表示方法,,,1.,数组表示法：对于完全二元树，空间效率好；其他二元树，要浪费大量空间,,,2.,链表法：结构简单，有效。链表中每个结点有三个信息段，,LCHILD,DATA,和,RCHILD,,③,堆,：堆是一棵完全二元树，它的每个结点的值至少和该结点的儿子们（如果存在的话）的值一样大（,max-,堆）（或小，,min-,堆）。,,,,④,二分检索树,：二分检索树Ｔ是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：,,,·,Ｔ的左子树的所有元素比根结点中的元素小；,,,·,Ｔ的右子树的所有元素比根结点中的元素大；,,,·,Ｔ的左子树和右子树也是二分检索树。,,

31、,,注：二分检索树要求树中所有结点的元素值互异,,,,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},,合并运算： s1∪s2={1, 7, 8, 9, 2, 5, 10},,

32、查找运算： 元素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}；,,利用位运算可得出,,s1∪s2= {1, 1, 0, 0, 1, 0, 1, 1, 1, 1},,缺点：n很大，超过一个机器字长，而参与运算的集合的势很小时，运算与n成正比。,,方法二——集合元素表,,s1={1, 7, 8, 9};,,s2={2, 5, 10},,合并操作：| s1|+| s2|,,查找操作：最坏为|n|,

33、,方法三——树,,,数据结构,,字符数组,U={1, 2, 3, 4, 5, 6, 7, 8, 9, 10},,子集,s1={1, 7, 8, 9}; s2={2, 5, 10},,则用数组,Parent,表示集合,s1,和,s2,：数组中记录的是节点,U[i],的父节点在,Parent,中的位置,（,1,）,（,2,）,（,3,）,（,4,）,（,5,）,（,6,）,（,7,）,（,8,）,（,9,）,（,10,）,0,0,…,…,2,…,1,1,1,2,合并操作,U(1,2),后：（,Parent[1]=2,）,（,1,）,（,2,）,（,3,）,（,4,）,（,5,）,（,6,）,（,7

34、,）,（,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(n^2),,症结？合并操作！,,加权规则,,节点数少的树合并到节点

35、数多的树中。,,字符数组,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),

36、,注意：本例的查找耗时不是最坏情况,,最坏情况由引理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<=m

37、经,Union,合并后，,j,的父亲为,k,；如右图：,,则,T,的级数：,,1,）等于,k,的级数：,log(n-m),的下界,+1<=,（,logn,的下界,+1,）,,2,）或者等于（,j,的级数,+1,）：（,logm,的下界,+2,）,<=,（,log(n/2),的下界,+2,）,<=,（,logn,的下界,+1,）,,得证,,压缩规则,,更快的平均查找时间，适用于频繁查找操作,,例1.2 在下图示例中实现8次对元素8的查找，用Find(8)算法实现,,,总共20次，优于使用F的8*3=24次,,结论：对于m次Find和n次Union的混合序列（m>=n），处理时间接近O(m)，但稍

38、差。详细描述见引理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,i

39、1,,，,v,i2,),,，,,…,，,,,(,,v,im,，,,v,q,),是,E,（,G,）的边。,,路的长度,：组成路的边数。,,简单路径,：除了第一和最后一个结点可以相同以外，,,其它所有结点都不同。,,环,：第一个和最后一个结点相同的简单路。,,连通图,：在无向图中，如果每对结点之间都存在一条,,路，则称该图是连通的。,,子图,：是由,G,的结点集,V,的子集（记为,VB,）和边集,E,,,中连接,VB,中结点的边的子集所组成的图。,,连通分图,：一个图的最大连通子图。,,有向图的强连通性,：在有向图中，如果对于每一对结,,点,i,和,j,，既存在一条从,i,到,j,的路，又存在一条

40、从,j,,,到,i,的路，则称该有向图是强连通的。,,图的表示方法,邻接矩阵 邻接表,,1.5,递归和消去递归,1.,递归,,直接调用自己或间接通过一些语句调用自己,,递归是一种强有力的设计方法,,描述某些数学问题非常自然，易于证明算法,,递归的效率问题,,执行时间、空间消耗多,,,例,1.3,斐波那契,(Fibonacci),序列：,,,F,0,= F,1,= 1,,F,i,= F,i-1,+ F,i-2,,（,i>1),,,算法,1.7,求斐波那契数,,,procedure F(n),,//,返回第,n,个斐波那契数,//,,in

41、teger n,,if n<= 1 then return(1),,else return(F(n-1) + F(n-2)),,endif,,end F,,,算法效率：对,F(n-1),、,F(n-2),存在大量的重复计算,,改 进：保存中间结果,,例,1.4,欧几里得算法,,已知两个非负整数,a,和,b,，且,a,＞,b≥0,，求这两个数的最大公因数。,,辗转相除法,：若,b=0,，则,a,和,b,的最大公因数等于,a,；若,b,＞,0,，则,a,和,b,的最大公因数等于,b,和用,b,除,a,的余数的最大公因数。,,算法,1.8,求最大公因数,,,procedure GCD(

42、a,b) //,约定,a>b //,,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,：

43、,n,）中检索,x,,procedure SEARCH(i),,//,如果在,A,（,1,：,n,）中有一元素,A,（,k,）,=x,，则将其第一次出现的下标,k,返回，否则返回,0//,,global n,x,A(1:n),,case,,:i>n: return(0),,:A(i) = x; return(i),,:else: return(SEARCH(i+1)),,endcase,,end SEARCH,,2.,消去递归,直接递归的消去规则,：,,,基本思路,：将递归过程中出现递归调用的地方，用等价的,非递归代码,来代替，并对,return,语句,做适当处理。,,,13,条规则：,处理

44、直接递归调用中的递归代码和,return,语句，将之转换成等价的迭代代码。,,初始化,,,⑴ 在过程的开始部分，插入说明为栈的代码并将其初始化为空。在一般情况下，这个栈用来存放参数、局部变量和函数的值、每次递归调用的返回地址。,,⑵ 将标号,L,1,附于第一条可执行语句。然后对于每一处递归调用都用一组执行下列规则的指令来代替。,,处理递归调用语句,,⑶ 将所有参数和局部变量的值存入栈。,,,栈顶指针,可作为一个全程变量来看待。,,⑷ 建立第,i,个新标号,L,i,，并将,i,存入栈。这个标号的,i,值将用来计算返回地址。,,此标号放在规则⑺所描述的程序段中。,,⑸ 计算这次调用的各实在参数（可

45、能是表达式）的值，并把这些值赋给相应的形式参数。,,⑹ 插入一条无条件转向语句转向过程的开始部分：,,,Goto L,1,,对递归嵌套调用的处理,,,⑺ 如果这过程是函数，则对递归过程中含有此次函数调用的那条语句做如下处理：将该语句的此次函数调用部分用从栈顶取回该函数值的代码来代替，其余部分的代码按原描述方式照抄，并将⑷中建立的标号附于这条语句上。,,如果此过程不是函数，则将⑷中建立的标号附于⑹所产生的转移语句后面的那条语句。,,,以上步骤实现消去过程中的递归调用。下面对过程中出现,return语句,进行处理（纯过程结束处的end可看成是一条没有值与之联系的return语句）。,,对每个有,r

46、eturn,语句的地方，执行下述规则,：,,,⑻ 如果栈为,空,，则执行,正常返回,。,,⑼ 否则，将所有输出参数（带有返回值的出口参数，,out/inout,型）的当前值赋给栈顶上的那些对应的变量。,,⑽ 如果栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。,,⑾ 从栈中退出所有局部变量和参数的值并吧它们赋给对应的变量。,,⑿ 如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在,return,后面的表达式并将结果值存入栈顶。,,⒀ 用返回地址标号的下标实现对该标号的转向。,,例,1.6,递归调用示例,,求数组元素中的最大值,,算法,1.1

47、0,递归求取数组元素的最大值,,,procedure MAX1(i),,//,查找数组,A,中最大值元素，并返回该元素的最大下标。,//,,global integer n,A(1:n),j,k,,integer i,,if i A(j) then k←i,,else k←j,,endif,,else k←n,,endif,,,return(k),//,递归调用的返回,//,,end MAX1,,,``,,,,消去上例中的递归,,算法,1.11,使用上述的规则消去例,1.10,中的递归代码,,

48、,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

49、,i ←,i+1,,//,规则,5,， 计算参数值,//,,,goto L1,,//,规则,6,， 无条件转向算法的开始部分,//,,,L2,:,j,←STACK(top); top ←top-1;,,//,规则,7,， 处理函数调用，,,并将标号,2,赋于该语句上,//,,if A(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,，

50、 从,,栈中退出返回标号,//,,,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,

51、k,n;,,i,←k ←n,,while i>1 do,,i,←i-1,,if A(i) >A(k) then k,←i endif,,repeat,,return(k),,end MAX3,,不必死套,13,条规则，应具体情况具体分析,,,procedure GCD1(a,b) //,约定,a>b //,,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;

52、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). 执行

53、,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,,加法

54、,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;

55、 3,,if c=A[i] 1,,then found:=true,1,,else if c>A[i] 1,,then L:=i+1,1,,else U:=i-1,,},,if found,,then b-search:=i,,else b-search:=0 1,,},Logn+1,,算法设计与分析,,已知不重复且从小到大排列的m个整数的数组A[1...m]

56、,m=2,K,,,,K为正整数.对于给定的整数c,要求找到一个下标i,使得A[i]=c.找不到返回0.,例 题,1-1,function b-search(c,L,U),,{ if U

57、t = c then 1,,b-search:= index;,,else if element >c 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,

58、m=1,,11+T(,m,/2),m>1,T(m)=,解得,: T(m) =11·logm+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

59、 n=1 then 1,,A:=1 1,,else A:=A(n-1)+A(n-2) 6+F(n-1)+F(n-2),,};,,{ if n<0 then 1,,error,,else for i:=0 to n do,,,writeln (A(i)),(1+F(,i,)),,};,设,F(n),是函数,A,在最坏情况下的时间复杂性,,,则,F(n),满足如下递归方程,:,设过程seg在最坏情况

60、下的时间复杂性为T(n),则 T(n)=1+ (1+F(,i,)),2 n=0,3 n=1,8+,F(n-1)+ F(n-2),n>1,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

61、),若,>0,使得,f,(,n,)=,,(n,log,b,a,+,,),且,,c,<1, 当n充分大时有,,a f,(,n/b,),,c,f,(,n,), 则 T(n)=,Θ,,(,f,(,n,)),设,a,0,,a,1,,…a,n,,..,是任意数列,,,称,f,(,x,)=,a,0,+,a,1,x,+…+,a,n,x,n,+…,为数列的,母函数,,若取数列为算法的时间复杂性函数,{ T(,n,) },,则其母函数为,:,,,f,(,x,)=T(0)+T(1),x,+…+,,T(,n,),x,n,…,,若能由,T(,n,),的递归方程求出,T(,n,),的母函数,,,其展开式第,

62、n,项系数即为,T(,n,).,递归方程解的渐进阶,,1).,母函数法,2).,迭代法,,,将递归方程的的右端项通过迭代展开成级数,,,然后估计级数和的渐进阶,.,3).,数学归纳法,(,代入法,),,,先估计递归方程的显式解,,,再用数学归纳法证明,.,,主方法,,递归式形式如下：,T,(,n,) =,aT,(,n,/,b,) +,f,(,n,) ,,其中,a,≥ 1,,b,> 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,,