计算机算法基础优秀PPT.ppt

序序专业基础课程：数据结构、计算机语言 操作系统、编译如何编写计算机程序：l数据结构+算法=程序l算法：计算机软件的“灵魂”算法是计算机科学和计算机应用的核心2023/4/15教材：计算机算法基础 余祥宣等编著 华中科技高校出版社参考书：算法设计与分析 王晓东编著 清华高校出版社 计算机算法导引设计与分析 卢开澄编著 清华高校出版社 Introduction To Algorithm 高教出版社，MIT Press 学时：32+8学时2023/4/15章节支配章节支配l第一章 导引与基本数据结构 l其次章 分治法 l第三章 贪心方法 l第四章 动态规划 l第五章 检索与周游 l第六章 回溯法l第七章 分枝-限界l第八章 NP-问题?l 2023/4/15第一章第一章 导引与基本数据结构导引与基本数据结构1.1 算法的定义及特性1.什么是算法？算法如数字、计算一样，是一个基本概念。算法是解一确定类问题的随意一种特殊的方法。在计算机科学中，算法是运用计算机解一类问题的精确、有效方法的代名词；算法是一组有穷的规则，它规定了解决某一特定类型 问题的一系列运算。2023/4/152.算法的五个重要特性 确定性、能行性、输入、输出、有穷性1）确定性：算法的每种运算必须要有准确的定义，不能有二义性。例：不符合确定性的运算 5/0 将6或7与x相加 未赋值变量参与运算2023/4/152）能行性 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在“有限”的时间内完成。例：整数的算术运算是“能行”的 实数的算术运算是“不能行”的2023/4/153）输入 每个算法有0个或多个输入。这些输入是在算法起先之前给出的量，取自于特定的对象集合定义域（或值域）4）输出 一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。2023/4/155）有穷性 一个算法总是在执行了有穷步的运算之后终止。计算过程：只满足确定性、能行性、输入、输出四个特性的一组规则。算法和计算过程的区分：计算过程：操作系统(不终止的运行过程)算法是“可以终止的计算过程”算法的时效性：只能把在相当有穷步内终止的算法投 入到计算机上运行2023/4/154.我们的主要任务 算法学习将涉及5个方面的内容：1）设计算法：创建性的活动 2）表示算法：思想的表示形式，SPARKS语言 3）确认算法：证明算法对全部可能的合法输入都能得出正确的答案。算法证明：证明算法的正确性，与语言无关 程序证明：证明程序的正确性 4）分析算法：对算法的时、空特性做定量分析，以了解算法的好坏 5）测试程序：调试：“调试只能指出有错误，而不能指出它们不存在错误”作时空分布图：验证分析结论，优化算法设计 本课程集中于学习算法的设计与分析。通过学习，驾驭计算机算法设计和分析基本策略与方法，为设计更困难、更有效的算法奠定基础2023/4/155.课程关系 数据结构 程序设计语言：结构化设计 数学基础 非数值计算领域的基本学问2023/4/151.2 分析算法1.分析算法的目的 在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避开无益的人力和物力奢侈。算法分析是计算机领域的“古老”而“前沿”的课题。2023/4/152.重要的假设和约定1）计算机模型的假设 计算机形式理论模型：Turing机模型 通用计算机模型：依次计算机 有足够的“内存”能在固定的时间内存取数据单元 2023/4/152）计算的约定 算法的执行时间=fi*ti 其中，fi是算法中用到的某种运算i的次数称为该运算的“频率计数”ti是该运算执行一次所用的时间 与程序语言和硬件有关 确定：运用何种运算及其执行时间。从运算的“时间特性”上将运算的分类：时间囿界于常数的运算：基本算术运算，如整数、浮点数的加、减、乘、除 字符运算、赋值运算、过程调用等 特点：尽管每种运算的执行时间不同，但一般只花一个 固定量的时间（单位时间）就可完成。2023/4/152）计算的约定（续）其他运算：字符串操作：与字符串中字符的数量成正比 记录操作：与记录的属性数、属性类型等有关 特点：运算时间无定量。如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。如：tstring=Length（String）*tchar2023/4/153）工作数据集的选择编制能够反映算法在最好、平均、最坏状况下工作的数据配置。然后运用这些数据配置运行算法，以了解算法的性能。编制测试数据是程序测试与算法分析中的关键技术之一。作为算法分析的数据集：反映算法的典型特征 作为程序正确性及性能测试的数据集：测试程序的对错，反映对性能指标产生影响的方面,如边界值2023/4/153.如何进行算法分析？对算法进行全面分析，可分两个阶段进行：事前分析：求算法的一个时间/空间限界函数，即通过对算 法的“理论”分析，得出关于算法时间和空间特性 的特征函数（、）与计算机物理软硬 件没有干脆关系。事后测试：将算法编制成程序后实际放到计算机上运行，收集其执行时间和空间占用等统计资料，进行 分析推断干脆与物理实现有关。2023/4/151）事前分析目的：试图得出关于算法特性的一种形式描 述，以“理论上”衡量算法的“好坏”。如何给出反映算法特性的描述？统计算法中各种运算的执行状况，包括：引用了哪些运算 每种运算被执行的次数 该种运算执行一次所花费的时间等。算法的执行时间=fi*ti2023/4/15l频率计数 频率计数：算法中语句或运算的执行次数。例：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次 2023/4/15一条语句在整个程序运行时实际执行时间=频率计数*每执行一次该语句所需的时间在事前分析中，只限于确定与所运用的机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。2023/4/15l数量级 l 衡量频率计数的“大小”的一种测度l 语句的数量级：语句的执行频率l 例：1，n，n2l 算法的数量级：算法所包含的全部语句的执行频率之和。l 数量级反映了算法困难度的最本质的特征。l例：假如求解同一个问题的三个算法分别具有n，n2，n3数量级。l 若n=10，则可能的执行时间将分别是10，100，1000个单l 位时间与环境因素无关。2023/4/15l 频率计数的函数表示l 就计算时间而言，事前分析阶段求得算法在频率计数l上的函数表示与规模n有关的函数形式，记为：g(n)l 不同的算法，g(n)的具体形式是不同的，如l logn，nlogn，n2等l g(n)的一般形式：关于n的简洁函数式l “实际”能够得到的：l 1)函数式的最高次项l 2)最高次项与函数整体的关系。l空间特性分析（与时间特性的分析类似，略）2023/4/152）事后测试目的：运行程序，统计执行实际耗费的精确的时间与空间，与事前分析的结论进行比较，验证从前的分析结论包括正确性、执行性能等，比较、优化所设计的算法。分析手段：作时、空性能分布图2023/4/154.计算时间的渐近表示记：算法的实际计算时间为f(n)，计算时间的限界函数为g(n)其中，n是输入或输出规模的某种测度。f(n)表示算法的“实际”执行时间与机器及语言有关。g(n)是事前分析的结果一个形式简洁的函数，如nm，logn，2n，n!等。是与频率计数有关、而与机器及语言无 关的函数。以下给出算法执行时间：上界（）、下界（）、“平均”（）的定义。2023/4/151）上界函数定义1 假如存在两个正常数c和n0，对于全部的nn0，有|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)。2023/4/15多项式定理 定理1 若A(n)=amnm+a1n+a0是一个m次多项式，则有 A(n)=(nm)即：变量n的固定阶数为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|则，定理得证。2023/4/15计算时间的数量级的大小对算法的有效性有确定性的影响 例：假设解决同一个问题的两个算法，它们都有n个输入,计算时间的数量级分别是n2和nlogn。则，n=1024：分别须要1048576和10240次运算。n=2048：分别须要4194304和22528次运算。分析：同等规模下的计算量比较：规模增大状况下的比较：在n加倍的状况下，一个(n2)的算法计算时间增长4倍，而一个(nlogn)算法则只用两倍多一点的时间即可完成。2023/4/15多项式时间算法和指数时间算法多项式时间算法：可用多项式（函数）对其计算时间限界 的算法。常见的多项式限界函数有：(1)(logn)(n)(nlogn)(n2)(n3)指数时间算法：计算时间用指数函数限界的算法 常见的指数时间限界函数：(2n)(n！)0。2023/4/152023/4/15l 特殊形态的二元树l 满二元树：深度为k且有2k-1个结点的二元树l 2023/4/15 完全二元树：一棵有n个结点深度为k的二元树，当它的 结点相当于深度为k的满二元树中编号为1到 n的结点时，称该二元树是完全的。完全二元树的叶子结点至多出现在相邻的两级上。完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理1.2）。2023/4/15 堆：堆是一棵完全二元树，它的每个结点的值至少和 该结点的儿子们（假如存在的话）的值一样大 （max-堆）（或小，min-堆）。二分检索树：二分检索树是一棵二元树，它或者为空，或者每个结点含有一个可以比较大小的数据元素，且 有：的左子树的全部元素比根结点中的元素小；的右子树的全部元素比根结点中的元素大；的左子树和右子树也是二分检索树。注：二分检索树要求树中全部结点的元素值互异2023/4/153.图 图由称之为结点和边的两个集合组成，记为 G=（V，E）其中，是一个有限非空的结点集合；是结点对偶的集合，的每一对偶表示的一条边。2023/4/15有关图的的重要概念l无向图：边表示为（，）l有向图：边表示为，l成本：带有成本的图称为网络（带权图）l邻接l结点的度（出度入度）l路径：由结点vp到vq的一条路（path）是结点 vp，vi1，vi2，vim，vq的一个序列，它使得 (vp，vi1)，(vi1，vi2)，(vim，vq)是E（G）的边。l路的长度：组成路的边数。2023/4/15l简洁路径：除了第一和最终一个结点可以相同以外，其它l 全部结点都不同。l环：第一个和最终一个结点相同的简洁路。l连通图：在无向图中，假如每对结点之间都存在一条路径，则l 称该图是连通的。l子图：是由G的结点集V的子集（记为VB）和边集E中连接VBl 中结点的边的子集所组成的图。l连通分图：一个图的最大连通子图。l有向图的强连通性：在有向图中，假如对于每一对结点i和j，l 既存在一条从i到j的路，又存在一条从jl 到i的路，则称该有向图是强连通的。2023/4/15图的表示方法l邻接矩阵 邻接表2023/4/151.5 递归和消去递归1.递归l 递归是一种强有力的设计方法l 递归的效率问题2023/4/15 例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 GDC 例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;2023/4/15例1.5 用递归策略设计的检索算法 已知元素x和元素表A（1：n），推断x是否等于A中某元素的值。算法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 SEARCH2023/4/152.消去递归干脆递归的消去规则：基本思路：将递归调用的地方用等价的非递归代码来代替，并对return语句做适当处理。13条规则：处理干脆递归调用和return语句，将之转换成等价的迭代代码。初始化 在过程的起先部分，插入说明为栈的代码并将其初始化为空。在一般状况下，这个栈用来存放参数、局部变量和函数的值、每次递归调用的返回地址。将标号L1附于第一条可执行语句。然后对于每一处递归调用都用一组执行下列规则的指令来代替。2023/4/15l 处理递归调用语句l 将全部参数和局部变量的值存入栈。l 栈顶指针可作为一个全程变量来看待。l 建立第i个新标号Li，并将i存入栈。这个标号的i值将用来计算返回地址。l 此标号放在规则所描述的程序段中。l 计算这次调用的各实在参数（可能是表达式）的值，并把这些值赋给相应的形式参数。l 插入一条无条件转向语句转向过程的起先部分：l goto L12023/4/15l 对退出一层递归调用后的处理l 假如这过程是函数，则对递归过程中含有此次函数调用l的那条语句做如下处理：将该语句的此次函数调用部分用从栈顶l取回该函数值的代码来代替，其余部分的代码按原描述方式照抄，并将中建立的标号附于这条语句上。l 假如此过程不是函数，则将中建立的标号附于所产生的转移语句后面的那条语句。l 以上步骤消去过程中的递归调用。下面对过程中出现return语句进行处理。l （纯过程结束处的end可看成是一条没有值与之联系的return语句）2023/4/15l 对每个有return语句的地方，执行下述规则：l 假如栈为空，则执行正常返回。l 否则，将全部输出参数（带有返回值的出口参数，out/inout型）的当前值赋给栈顶上的那些对应的变量。l 假如栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未运用的变量。l 从栈中退出全部局部变量和参数的值并吧它们赋给对应的变量。l 假如这个过程是函数，则插入以下指令，这些指令用来计算紧接在return后面的表达式并将结果值存入栈顶。l 用返回地址标号的下标实现对该标号的转向。2023/4/15例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 2023/4/15l消去上例中的递归l算法1.11 运用上述的规则消去例1.10中的递归代码l procedure MAX2(i)l local integer j,k;global integer n,A(1:n)l integer Il integer STACK(1:2*n)l top0 /规则1，声明栈的代码，并初始化为空/l L1:if i A(j)then k I else k j endif else k n endif2023/4/15 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，用返回 地址标号的下标实现对该标号的转向/endifend MAX2 2023/4/15l进一步优化和简化经过消去递归产生的迭代程序。2023/4/15