第一章--导引与基本数据结构-《计算机算法基础》课件.ppt

《第一章--导引与基本数据结构-《计算机算法基础》课件.ppt》由会员分享，可在线阅读，更多相关《第一章--导引与基本数据结构-《计算机算法基础》课件.ppt（100页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机算法基础算法的研究内容n问题是否可解q1930s 研究集中于判断特定问题在计算机上是否可解，基本方法为：选定一个计算模型，观察是否能在该模型上创建能解决问题的算法。这些计算模型包括：Post machines、Turing machines等。这一阶段的成果是：大部分问题为不可解。n高效率的解决方法q随着计算机的发展和数据资源的增加，算法研究转向针对可解的问题，找到高效率的解决方法。算法的应用n数据库中的检索n搜索引擎中的爬找器和检索n公共密钥加密和数字签名技术n优化问题q最短路径q资源分配q章节安排n计算机算法基础，余祥宣、崔国华、邹海明著，华中科技大学出版社 n第一章 导引与基本数据

2、结构 n第二章 分治法 n第三章 贪心方法 n第四章 动态规划 n第五章 检索与周游n第六章 回溯法n第七章 分枝-限界n第八章 NP-问题 第一章 导引与基本数据结构1.1 算法的定义及特性1.什么是算法？算法是解一确定类问题的任意一种特殊的方法。在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词：算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。2.算法的五个重要特性 确定性、能行性、输入、输出、有穷性1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。例：不符合确定性的运算n 5/0 n 将6或7与x相加n 未赋值变量参与运算2）能行性 算法中有待实

3、现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。例：整数的算术运算是“能行”的 实数的算术运算是“不能行”的5）有穷性 一个算法总是在执行了有穷步的运算之后终止。计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。n 准确理解算法和计算过程的区别：不能终止的计算过程：操作系统 算法是“可以终止的计算过程”算法的时效性：只能把在相当有穷步内终止的算法投 入到计算机上运行3.我们的主要任务 算法学习将涉及5个方面的内容：1）设计算法：创造性的活动 2）表示算法：思想的表示形式 3）确认算法：证明算法的正确性 程序的证明 4）分析算法：算法时空特性分

4、析 5）测试程序：调试和作出时空分布图 本课程集中于学习算法的设计与分析。通过学习，掌握计算机算法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基础2.重要的假设和约定1）计算机模型的假设n Turing机模型：计算机形式理论模型 n 通用计算机模型：单处理器 有足够的“内存”能在固定的时间内存取数据单元2）计算的约定（续）计算的约定（续）其他运算：字符串操作：与字符串中字符的数量成正比 记录操作：与记录的属性数、属性类型等有关 特点：运算时间无定量 如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。如：Tstring=Length（String）*tcharn算法的执

5、行时间=Fi*tiq其中，Fi是算法中用到的某种运算i的次数，ti是该运算执行一次所用的时间。3）工作数据集的选择n编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。n测试数据集的生成n作为算法分析的数据集：典型特征n作为程序性能测试的数据集：对执行指标产生影响的性质1）事前分析n目的：试图得出关于算法执行特性的一种形式描 述，以“理论上”衡量算法的“好坏”。n如何给出反映算法执行特性的描述？最直接方法：统计算法中各种运算的执行情况，包括：运用了哪些运算 每种运算被执行的次数 该种运算执行一次所花费的时间等。算法的执行时间=Fi*tin频率

6、计数 例：xx+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)：xx+y执行了1次 (b)：xx+y执行了n次 (c)：xx+y执行了n2次 定义：频率计数：一条语句或一种运算在算法（或程序）体中的执行次数。算法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-

7、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 n(8,5,4,9)n(8,5,4,9)n(5,8,4,9)n(5,8,4,9)n(4,5,8,9)n(4,5,8,9)一条语句在整个程序运行时实际执行时间=频率计数*每执行一次该语句所需的时间n 如何刻画算法执行特性的形式描述实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，没有统一的描述模型。在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。n数量级

8、 语句的数量级：语句的执行频率 例：1，n，n2 算法的数量级：算法所包含的所有语句的执 行频率之和。算法的数量级从本质上反映了一个算法的执行特性。例：假如求解同一个问题的三个算法分别具有n，n2，n3数 量级。若n=10，则可能的执行时间将分别是10，100，1000个单 位时间与环境因素无关。2）事后测试n目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论包括正确性、执行性能等，比较、优化所设计的算法。n分析手段：作时、空性能分布图4.计算时间的渐近表示计算时间的渐近表示记：算法的计算时间为f(n)数量级限界函数为g(n)其中，n n是输入或输出规模的某种测度。n f(n)表

9、示算法的“实际”执行时间与机器及语言有关。n g(n)是形式简单的函数，如nm，logn，2n，n!等。是事前分析中通过对计算时间或频率计数统计分析所得的、与机器及语言无关的函数。以下给出算法执行时间：上界（）、下界（）、“平均”（）的定义。1）上界函数）上界函数定义1 如果存在两个正常数c和n0，对于所有的nn0，有|f(n)|c|g(n)|则记作f(n)=(g(n)含义：n如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数。f(n)的数量级就是g(n)。n试图求出最小的g(n)，使得f(n)=(g(n)

10、。n 计算时间的数量级对算法有效性的影响 数量级的大小对算法的有效性有决定性的影响。例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n2和nlogn。则，n=1024：分别需要和10240次运算。n=2048：分别需要和22528次运算。分析：在n加倍的情况下，一个(n2)的算法计算时间增长4 倍，而一个(nlogn)算法则只用两倍多一点的时间即 可完成。算法2.8 归并分类 procedure MERGESORT(low,high)/A(low:high)是一个全程数组，它含有high-low+10个待分类的元素/integer low,high if lowhig

11、h then mid /计算中分点/call MERGESORT(low,mid)/在第一个子集合上分类(递归)/call MERGESORT(mid+1,high)/在第二个子集合上分类(递归)/call MERGE(low,mid,high)/归并已分类的两子集合/endif end MERGESORT 算法分类（计算时间）算法分类（计算时间）多项式时间算法：可用多项式（函数）对其计算时间限界的算法。常见的多项式限界函数有：(1)(logn)(n)(nlogn)(n2)(n3)指数时间算法：计算时间用指数函数限界的算法 常见的指数时间限界函数：(2n)(n！)0。特殊形态的二元树n 满二元

12、树：深度为k且有2k-1个结点的二元树 n完全二元树：一棵有n个结点深度为k的二元树，当它的结点相当于深度为k的满二元树中编号为1到n的结点时，称该二元树是完全的。完全二元树的叶子结点至多出现在相邻的两级上。完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理1.2）。二元树的表示方法二元树的表示方法 1.数组表示法：对于完全二元树，空间效率好；其他二元树，要浪费大量空间 2.链表法：结构简单，有效。链表中每个结点有三个信息段，LCHILD,DATA和RCHILD 堆：堆是一棵完全二元树，它的每个结点的值至少和该结点的儿子们（如果存在的话）的值一样大（max-堆）（或小，min-堆）。二

13、分检索树：二分检索树是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：的左子树的所有元素比根结点中的元素小；的右子树的所有元素比根结点中的元素大；的左子树和右子树也是二分检索树。注：二分检索树要求树中所有结点的元素值互异3.树的应用不相交集合的合并及搜索问题 n问题描述：q给定一个全集U，该集合包含n个元素q很明显该集合包含多个不相交的子集q某些应用需要实现这些不相交子集的合并、查找操作，并且这些操作最终可形成序列q如何高效率实现这些操作序列就是我们要解决的问题集合操作举例nn=10，U=1,2,3,4,5,6,7,8,9,10ns1=1,7,8,9;s2=2,5,

14、10;s3=3,4,6n合并运算：s1s2=1,7,8,9,2,5,10n查找运算：元素4包含在s1,s2,s3的哪个集合中？方法一位向量n方法一：位向量 n s1=1,0,0,0,0,0,1,1,1,0；n s2=0,1,0,0,1,0,0,0,0,1；n利用位运算可得出ns1s2=1,1,0,0,1,0,1,1,1,1n缺点：n很大，超过一个机器字长，而参与运算的集合的势很小时，运算与n成正比。方法二集合元素表 ns1=1,7,8,9;ns2=2,5,10n合并操作：|s1|+|s1|n查找操作：最坏为|n|方法三树 数据结构n字符数组U=1,2,3,4,5,6,7,8,9,10n子集s1

15、=1,7,8,9;s2=2,5,10n则用数组Parent表示集合s1和s2：数组中记录的是节点Ui的父节点在Parent中的位置（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）0021112合并操作U(1,2)后：（Parent1=2）（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）2021112查找元素F(9)U操作为常量时间，F操作则与查找元素在集合树中的层数有关。U和F的性能问题退化树 n问题描述：有集合如下：n （1）（2）（n）n 0 0 0n依次作下列操作：U(1,2),F(1),U(2,3),F(1),U(n-1,n)n按照算法U和F，最终得到的树及

16、时间耗费分析nU：每次都是常量时间，因此总共是O(n-1)nF(1)：2+3+(n-1)，因此是O(n2)n症结？合并操作！加权规则 n节点数少的树合并到节点数多的树中。q字符数组U=1,2,3,4,5,6,7,8,9,10q子集s1=1,7,8,9;s2=2,5,10（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）-4-321112Union F序列演示分析nUnion(1,2),F(1),Union(2,3),F(1),Union(n-1,n)nUnion合并的开销较u要大，但仍然是常量时间n每次查找1耗费时间为2，常量时间，则执行n-2次查找耗费时间为O(n)n注意：本例的

17、查找耗时不是最坏情况n最坏情况由引理1.3给出引理1.3n引理1.3 设T是一棵由算法union所产生的有n个节点的树。在T中没有节点的级数会大于（logn的下界+1）n证明：n=1，显然引理为真；ni为T的级数，假设当i=n-1时，引理为真，现证对于i=n，引理也为真；n令k和j是形成树T的最后一次合并，即Union(k,j)；n用count()表示数的节点数，假设count(j)=m，那么count(k)=n-m；n不失一般性，可假设1=mn/2，则有 m=n-m；n那么经Union合并后，j的父亲为k；如右图：n则T的级数：n1）等于k的级数：log(n-m)的下界+1=（logn的下界

18、+1）n2）或者等于（j的级数+1）：（logm的下界+2）=（log(n/2)的下界+2）=n），处理时间接近O(m)，但稍差。详细描述见引理1.4。例1.24.图图 图由称之为结点和边的两个集合组成，记为G=（V，E）。其中，是一个有限非空的结点集合；是结点对偶的集合，的每一对偶表示的一条边。有关图的的重要概念有关图的的重要概念n无向图：边的表示（，）n有向图：边的表示，n成本：带有成本的图称为网络n邻接：n结点的度（出度入度）n路径：由结点vp到vq的一条路（path）是结点 vp，vi1，vi2，vim，vq的一个序 列，它使得(vp，vi1)，(vi1，vi2)，(vim，vq)是E

19、（G）的边。n路的长度：组成路的边数。n简单路径：除了第一和最后一个结点可以相同以外，其它所有结点都不同。n环：第一个和最后一个结点相同的简单路。n连通图：在无向图中，如果每对结点之间都存在一条 路，则称该图是连通的。n子图：是由G的结点集V的子集（记为VB）和边集E 中连接VB中结点的边的子集所组成的图。n连通分图：一个图的最大连通子图。n有向图的强连通性：在有向图中，如果对于每一对结 点i和j，既存在一条从i到j的路，又存在一条从j 到i的路，则称该有向图是强连通的。图的表示方法图的表示方法n邻接矩阵 邻接表1.5 递归和消去递归递归和消去递归1.递归n直接调用自己或间接通过一些语句调用自

20、己n递归是一种强有力的设计方法q描述某些数学问题非常自然，易于证明算法n 递归的效率问题q执行时间、空间消耗多 例1.3 斐波那契(Fibonacci)序列：F0=F1=1 Fi=Fi-1+Fi-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递推递推递递

21、推推递递推推递递推推回回归归回回归归回回归归回归回归结果为结果为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 SEARCH2.消去递归消去递归直接递归的消去规则：基本思路：将递归过程中出现递归调用的地方，用等

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

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

24、常返回。否则，将所有输出参数（带有返回值的出口参数，out/inout型）的当前值赋给栈顶上的那些对应的变量。如果栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。从栈中退出所有局部变量和参数的值并吧它们赋给对应的变量。如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在return后面的表达式并将结果值存入栈顶。用返回地址标号的下标实现对该标号的转向。例1.6 递归调用示例 求数组元素中的最大值算法1.10 递归求取数组元素的最大值 procedure MAX1(i)/查找数组A中最大值元素，并返回该元素的最大下标。/global integ

25、er n,A(1:n),j,k integer i if i A(j)then ki else kj endif else kn endif return(k)/递归调用的返回/end MAX1 n消去上例中的递归n算法1.11 使用上述的规则消去例1.10中的递归代码 procedure MAX2(i)local integer j,k;global integer n,A(1:n)integer I integer STACK(1:2*n)top0 /规则1，声明栈的代码，并初始化为空/L1:if i A(j)then k I else k j endif else k n endif i

26、f 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，用返回 地址标号的下标实现对该标号的转向/endifend MAX2 n进一步优化和简化经过消去递归产生的迭代程序。算法1.12 算法1.11的改进模型procedure MAX3(A,

27、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 repeatreturn(a)end GCD

28、2递归式分析n代换法q猜测q验证q找到常量的范围n递归树n主定理q三种情况q需要记忆代换法例子一nT(n)=2T(n/2)+nn假设：T(1)=(1)n猜测上界函数为：O(nlgn)n证明：q有T(k)cnlgn，k n q则T(n)2c(n/2)lg(n/2)+n cnlg(n/2)+nq cnlgn-cnlg2+n cnlgn-(cn-n)cnlgn n常数：c大于等于1代换法避免陷阱nT(n)=2T(n/2)+nn假设：T(1)=(1)n猜测上界函数为：O(n)n证明：q有T(k)cn，k n q则T(n)2c(n/2)+n cn+n O(n)错！n常数：c大于等于1代换法例子二（小技巧

29、）nT(n)=2T(n/2)+1n假设：T(1)=(1)n猜测上界函数为：O(n)n证明：q有T(k)cn，k=0T(n)2(c(n/2)-b)+1=cn-(2b-1)cnn常数：b大于等于1/2，c取足够大递归树方法nT(n)=3T(n/4)+cn2nT(n)=T(n/3)+T(2n/3)+O(n)主方法n递归式形式如下：T(n)=aT(n/b)+f(n),其中 a 1,b 1,f(n)是渐近的正函数n主定理：比较 f(n)和 nlogba:qf(n)=O(nlogba),常数 0.T(n)=(nlogba)qf(n)=(nlogba lgkn),常数 k 0.T(n)=(nlogba lgk+1n)qf(n)=O(nlogba+),常数 0.T(n)=(f(n)主方法例子nT(n)=9T(n/3)+nnT(n)=T(2n/3)+1nT(n)=2T(n/2)+nlgn