《计算机算法基础第一章教案资料.ppt》由会员分享，可在线阅读，更多相关《计算机算法基础第一章教案资料.ppt（102页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机算法基础第一章算法的应用n数据库中的检索n搜索引擎中的检索n公共密钥加密和数字签名技术n优化问题q最短路径q资源分配q章节安排n计算机算法基础，余祥宣、崔国华、邹海明著，华中科技大学出版社 n第一章 导引与基本数据结构 n第二章 分治法 n第三章 贪心方法 n第四章 动态规划 n第五章 检索与周游n第六章 回溯法n第七章 分枝-限界n第八章 NP-问题 预备知识n数学：集合、证明方法（直接、间接、反证、反例、归纳假设）、对数基础、FLOOR&CEILING函数、阶乘、递归关系n数据结构：链接表、图、树、二元树第一章 导引与基本数据结构1.1 算法的定义及特性1.什么是算法？一系列将问题的
2、输入转换为输出的计算或操作步骤一系列将问题的输入转换为输出的计算或操作步骤。2.算法的五个重要特性 确定性、能行性、输入、输出、有穷性1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。例：不符合确定性的运算n 5/0 n 将6或7与x相加n 未赋值变量参与运算2）能行性 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。例：整数的算术运算是“能行”的 实数的算术运算是“不能行”的3）输入 每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合定义域（或值域）4）输出 一个算法产生一个或多个输出，这些输出是同输入有某种特定关
3、系的量。5）有穷性 一个算法总是在执行了有穷步的运算之后终止。计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。n 准确理解算法和计算过程的区别：不能终止的计算过程：操作系统 算法是“可以终止的计算过程”算法的时效性：只能把在相当有穷步内终止的算法投 入到计算机上运行3.我们的主要任务 算法学习将涉及5个方面的内容：1）设计算法：创造性的活动 2）表示算法：思想的表示形式 3）确认算法：证明算法的正确性 程序的证明 4）分析算法：算法时空特性分析 5）测试程序：调试和作出时空分布图 本课程集中于学习算法的设计与分析。通过学习，掌握计算机算法设计和分析基本策略与方法，为
4、设计更复杂、更有效的算法奠定基础4.算法描述语言自然语言自然语言,数学语言数学语言,流程图流程图,程序设计语言等等程序设计语言等等.5.问题的求解过程2)建立数学模型1)问题的陈述3)算法设计用科学规范的语言用科学规范的语言,对所求解的问题做准确的描述对所求解的问题做准确的描述.通过对问题的分析通过对问题的分析,找出其中的所有操作对象及操作对象之间找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述的关系并用数学语言加以描述.根据数学模型设计问题的计算机求解算法根据数学模型设计问题的计算机求解算法.4)算法的正确性证明5)算法的程序实现6)算法分析证明算法对一切合法输入均能在有限次计
5、算后产生正确输出证明算法对一切合法输入均能在有限次计算后产生正确输出.对执行该算法所消耗的计算机资源进行估算对执行该算法所消耗的计算机资源进行估算.将算法正确地编写成机器语言程序将算法正确地编写成机器语言程序.1.2 1.2 分析算法分析算法1.分析算法的目的 在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。算法分析是计算机领域的古老而前沿的课题。进行算法分析的基本技术：抽象2.重要的假设和约定1）计算机模型的假设n Turing机模型：计算机形式理论模型 n 通用计算机模型：单处理器 有足够
6、的“内存”能在固定的时间内存取数据单元2）计算的约定n确定使用什么样的运算及其执行时间。n从计算时间上，运算的分类：时间囿界于常数的运算：尽管每种运算的执行时间不同，但一般只花 一个固定量的时间（单位时间）就可完成。基本算术运算，如整数、浮点数的加、减、乘、除 字符运算 赋值运算 过程调用等2）计算的约定（续）计算的约定（续）其他运算：字符串操作：与字符串中字符的数量成正比 记录操作：与记录的属性数、属性类型等有关 特点：运算时间无定量 如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。如：Tstring=Length（String）*tcharn算法的执行时间=Fi*tiq其中
7、，Fi是算法中用到的某种运算i的次数，ti是该运算执行一次所用的时间。3）工作数据集的选择n编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。n测试数据集的生成n作为算法分析的数据集：典型特征n作为程序性能测试的数据集：对执行指标产生影响的性质3.如何进行算法分析？对算法进行全面分析，可分两个阶段进行：n事前分析：就算法本身，通过对其执行性能的理论分析，得出关于算法特性时间和空间的一个特征 函数（、）与计算机物理软硬件没有 直接关系。n事后测试：将算法编制成程序后实际放到计算机上运行，收集其执行时间和空间占用等统计资料，进行 分析判断直接与
8、物理实现有关。1）事前分析n目的：试图得出关于算法执行特性的一种形式描 述，以“理论上”衡量算法的“好坏”。n如何给出反映算法执行特性的描述？最直接方法：统计算法中各种运算的执行情况，包括：运用了哪些运算 每种运算被执行的次数 该种运算执行一次所花费的时间等。算法的执行时间=Fi*tin频率计数 例：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次 定义：频率计数：
9、一条语句或一种运算在算法（或程序）体中的执行次数。算法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 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)一
10、条语句在整个程序运行时实际执行时间=频率计数*每执行一次该语句所需的时间n 如何刻画算法执行特性的形式描述实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，没有统一的描述模型。在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。n数量级 语句的数量级：语句的执行频率 例：1，n，n2 算法的数量级：算法所包含的所有语句的执 行频率之和。算法的数量级从本质上反映了一个算法的执行特性。例：假如求解同一个问题的三个算法分别具有n，n2，n3数 量级。若n=10，则可能的执行时间将分别是10，100，1000个单 位时间与环境因素无关。n 计算时
11、间/频率计数的表示函数 通过事前分析给出算法计算时间（频率计数）的一个函数表示形式，一般记为与输入规模n有关的函数形式：f(n)注：最高次项与函数整体的关系n空间特性分析（略）2）事后测试n目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论包括正确性、执行性能等，比较、优化所设计的算法。n分析手段：作时、空性能分布图4.计算时间的渐近表示计算时间的渐近表示记：算法的计算时间为f(n)数量级限界函数为g(n)其中，n n是输入或输出规模的某种测度。n f(n)表示算法的“实际”执行时间与机器及语言有关。n g(n)是形式简单的函数，如nm，logn，2n，n!等。是事前分析中通过对
12、计算时间或频率计数统计分析所得的、与机器及语言无关的函数。以下给出算法执行时间：上界（）、下界（）、“平均”（）的定义。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)。n多项式定理:定理1 若A(n)=amnm+a1n+a0是一个m次多项 式，则有A(n)=(nm)即：变量n的固定阶数为
13、m的任一多项式，与此多 项式的最高阶nm同阶。证明：取n0=1,当nn0时，有|A(n)|am|nm+|a1|n+|a0|(|am|+|am-1|/n+|a0|/nm)nm (|am|+|am-1|+|a0|)nm 令c=|am|+|am-1|+|a0|则，定理得证。n 计算时间的数量级对算法有效性的影响 数量级的大小对算法的有效性有决定性的影响。例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n2和nlogn。则，n=1024：分别需要1048576和10240次运算。n=2048：分别需要4194304和22528次运算。分析：在n加倍的情况下，一个(n2)的算法
14、计算时间增长4 倍，而一个(nlogn)算法则只用两倍多一点的时间即 可完成。算法2.8 归并分类 procedure MERGESORT(low,high)/A(low:high)是一个全程数组，它含有high-low+10个待分类的元素/integer low,high if lowhigh then mid /计算中分点/call MERGESORT(low,mid)/在第一个子集合上分类(递归)/call MERGESORT(mid+1,high)/在第二个子集合上分类(递归)/call MERGE(low,mid,high)/归并已分类的两子集合/endif end MERGESOR
15、TMerge算法示例n(4,5,8,9)|(1,2,6,7)(1,2,4,5,6,7,8,9)q参数：low=1;high=8;mid=4q(4,5,8,9)|(1,2,6,7)hjjjjhh(14256789)j 算法分类（计算时间）算法分类（计算时间）多项式时间算法：可用多项式（函数）对其计算时间限界的算法。常见的多项式限界函数有：(1)(logn)(n)(nlogn)(n2)(n3)指数时间算法：计算时间用指数函数限界的算法 常见的指数时间限界函数：(2n)(n！)0。特殊形态的二元树n 满二元树：深度为k且有2k-1个结点的二元树 n完全二元树：一棵有n个结点深度为k的二元树，当它的结
16、点相当于深度为k的满二元树中编号为1到n的结点时，称该二元树是完全的。完全二元树的叶子结点至多出现在相邻的两级上。完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理1.2）。二元树的表示方法二元树的表示方法 1.数组表示法：对于完全二元树，空间效率好；其他二元树，要浪费大量空间 2.链表法：结构简单，有效。链表中每个结点有三个信息段，LCHILD,DATA和RCHILD 堆：堆是一棵完全二元树，它的每个结点的值至少和该结点的儿子们（如果存在的话）的值一样大（max-堆）（或小，min-堆）。二分检索树：二分检索树是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且
17、有：的左子树的所有元素比根结点中的元素小；的右子树的所有元素比根结点中的元素大；的左子树和右子树也是二分检索树。注：二分检索树要求树中所有结点的元素值互异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,10;s3=3,4,6n合并运算：s1s2=1,7,8,9,2,5,10n查找运算：元素4包含
18、在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|+|s2|n查找操作：最坏为|n|方法三树 数据结构n字符数组U=1,2,3,4,5,6,7,8,9,10n子集s1=1,7,8,9;s2=2,5,10n则用数组Parent表示集合s1和s2：数组中记录的是节
19、点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，最终得到的树及时间耗费分析nU：每次都是常量时间，因此总共是O(n-1)nF(1)：2+3+(n-1)，因此
20、是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注意：本例的查找耗时不是最坏情况n最坏情况由引理1.3给出引理1.3n引理1.3 设T是一棵由算法unio
21、n所产生的有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的下界+1）n2）或者等于（j的级数+1）：（logm的下界+2）=（log(n/2)的下界+2）=
22、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（G）的边。n路的长度：组成路的边数。n简单路径：除了第一和最后一个结点可以相同以外，其它所有
23、结点都不同。n环：第一个和最后一个结点相同的简单路。n连通图：在无向图中，如果每对结点之间都存在一条 路，则称该图是连通的。n子图：是由G的结点集V的子集（记为VB）和边集E 中连接VB中结点的边的子集所组成的图。n连通分图：一个图的最大连通子图。n有向图的强连通性：在有向图中，如果对于每一对结 点i和j，既存在一条从i到j的路，又存在一条从j 到i的路，则称该有向图是强连通的。图的表示方法图的表示方法n邻接矩阵 邻接表1.5 递归和消去递归递归和消去递归1.递归n直接调用自己或间接通过一些语句调用自己n递归是一种强有力的设计方法q描述某些数学问题非常自然，易于证明算法n 递归的效率问题q执行
24、时间、空间消耗多 例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递推递推递递推推递递推推递递推推回回归归回回归归回回归归回归回归结果为结果为GCD(22,8)=2例1.5
25、 递归在非数值算法设计中的应用 已知元素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.消去递归消去递归直接递归的消去规则：基本思路：将递归过程中出现递归调用的地方，用等价的非递归代码来代替，并对return语句做适当处理。13条规则：处理直接递归调用中的递归代码
26、和return语句，将之转换成等价的迭代代码。n 初始化 在过程的开始部分，插入说明为栈的代码并将其初始化为空。在一般情况下，这个栈用来存放参数、局部变量和函数的值、每次递归调用的返回地址。将标号L1附于第一条可执行语句。然后对于每一处递归调用都用一组执行下列规则的指令来代替。n 处理递归调用语句 将所有参数和局部变量的值存入栈。栈顶指针可作为一个全程变量来看待。建立第i个新标号Li，并将i存入栈。这个标号的i值将用来计算返回地址。此标号放在规则所描述的程序段中。计算这次调用的各实在参数（可能是表达式）的值，并把这些值赋给相应的形式参数。插入一条无条件转向语句转向过程的开始部分：Goto L1
27、n 对递归嵌套调用的处理 如果这过程是函数，则对递归过程中含有此次函数调用的那条语句做如下处理：将该语句的此次函数调用部分用从栈顶取回该函数值的代码来代替，其余部分的代码按原描述方式照抄，并将中建立的标号附于这条语句上。如果此过程不是函数，则将中建立的标号附于所产生的转移语句后面的那条语句。以上步骤实现消去过程中的递归调用。下面对过程中出现return语句进行处理（纯过程结束处的end可看成是一条没有值与之联系的return语句）。n 对每个有return语句的地方，执行下述规则：如果栈为空，则执行正常返回。否则，将所有输出参数（带有返回值的出口参数，out/inout型）的当前值赋给栈顶上的
28、那些对应的变量。如果栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。从栈中退出所有局部变量和参数的值并吧它们赋给对应的变量。如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在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
29、 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 if top=0 then return(k)/规则8，如果栈空，则正常返回/else addr
30、 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,n)integer i,k,n;i k n while i1 do i i-1 if A(i)
31、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 GCD2 渐进分析 时间复杂性渐进阶分析的规则:(最坏情况)1).赋值,比较,算术运算,逻辑运算,读
32、写单个变量(常量)只需1单位时间 2).执行条件语句 if c then S1 else S2 的时间为TC+max(TS1,TS2).3).选择语句 case A of a1:s1；a2:s2；.；am:sm 需要的时间为 max（TS1,TS2,.,TSm）.4).访问数组的单个分量或纪录的单个域需要一个单位时间一个单位时间.5).执行for循环语句的时间=执行循环体时间执行循环体时间*循环次数循环次数.6).while c do s(repeat s until c)语句时间=(Tc+Ts)*循环次数循环次数.7).用goto从循环体内跳到循环体末或循环后面的语句时,不需额外时间 8).
33、过程或函数调用语句 对非递归调用,根据调用层次由里向外用规则1-7进行分析；对递归调用,可建立关于T(n)的的递归方程,求解该方程得到T(n).例例 题题1-1 算法1-2:二分查找(假定c是A的最后一元)例例 题题 1-1分析:问题规模为n,元运算执行时间设为赋值a,判断t,加法s,除法d,减法b.最坏情况Tmax(n)=6a+4t+2s+d+(2a+2s+3t+d)lognfunction 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 1then found
34、:=true 1else 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=2K,K为正整数.对于给定的整数c,要求找到一个下标i,使得Ai=c.找不到返回0.例例 题题 1-1function 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
35、+1,U);3+T(m/2);设T(m)是b-search在最坏情况下的时间复杂性,则T(m)满足如下递归方程:2 2 m=0 013 13 m=1 11+T(11+T(m/2)/2)m1T(m)=解得:T(m)=11logm+13=(logm)算法1-3:二分查找递归算法 求Fibonacci数列的前N项 a0,a1,aN 其中,a0=0,a1=1,ai=ai-1+ai-2算法1-4Procedure 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)+
36、F(n-2);if n1 n1F(n)=例例 题题 1-24).套用公式法 若递归方程形如:T(n)=aT(n/b)+f(n),可根据f(n)的不同情况套用公式 1)若0,使得 f(n)=O(n logb a-),则T(n)=(n logb a)2)若f(n)=(n logb a),则T(n)=(n logb a logn)3)若0,使得f(n)=(n logb a+),且 c 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此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢