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