《计算机算法基础(第2章).ppt》由会员分享，可在线阅读，更多相关《计算机算法基础(第2章).ppt（58页珍藏版）》请在三一办公上搜索。
1、章节安排,第 2 章 导引与基本数据结构 第 3 章 递归算法 第 4 章 分治法 第 5 章 贪心方法 第 6 章 动态规划 第 7 章 检索与周游第 8 章 回溯法第 9 章 分枝-限界第10章 NP-问题第11章 并行算法,算法问题举例,问题描述在N件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2Wn，与之相对应的价值为P1,P2Pn。求出获得最大价值的方案。,第 2 章 导引与基本数据结构,2.1 算法的定义及特性1.什么是算法？算法如数字、计算一样，是一个基本概念。算法是解一确定类问题的任意一种特殊的方法。在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代
2、名词：算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。,2.算法的五个重要特性 确定性、能行性、输入、输出、有穷性,1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。例：不符合确定性的运算 5/0 6+x 未赋值变量参与运算,2）能行性 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。例：整数的算术运算是“能行”的 实数的算术运算是“不能行”的,3）输入 每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合定义域（或值域）,4）输出 一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。,5）
3、有穷性 一个算法总是在执行了有穷步的运算之后终止。计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。准确理解算法和计算过程的区别：不能终止的计算过程：操作系统 算法是“可以终止的计算过程”算法的时效性：只能把在相当有穷步内终止的算法投 入到计算机上运行,算法和程序,程序：一个计算机程序是对一个算法使用某种程序设计语言的具体实现任何程序设计语言都可以实现任何一个算法算法的有穷性意味着不是所有的计算机程序都是算法,3.我们的主要任务 算法学习将涉及5个方面的内容：1）设计算法：创造性的活动 2）表示算法：思想的表示形式 3）确认算法：证明算法的正确性 程序的证明 4）分析
4、算法：算法时空特性分析 5）测试程序：“调试只能指出有错误，而不能指出它们 不存在错误”本课程集中于学习算法的设计与实现。通过学习，掌握计算机算法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基础,被实践证明是有用的基本设计策略,算法所需时间和空间的定量分析,4.课程关系 数据结构、离散数学 程序设计语言：结构化设计 数学基础 非数值计算领域的基本知识,2.2 分析算法,计算机程序设计的核心目标：1、设计一个容易理解、编码和调试的算法2、设计一个能有效利用计算机资源的算法怎样度量效率？算法分析,1.分析算法的目的 在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任
5、务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。算法分析是计算机领域的古老而前沿的课题。进行算法分析的基本技术：抽象,2.重要的假设和约定1）计算机模型的假设 Turing机模型：计算机形式理论模型 通用计算机模型：顺序计算机 有足够的“内存”能在固定的时间内存取数据单元,2）计算的约定 算法的执行时间=Fi*ti 其中，Fi是算法中用到的某种运算i的次数，ti是该运算执行一次所用的时间。确定使用什么样的运算及其执行时间。从计算时间上，运算的分类：时间囿界于常数的运算：基本算术运算，如整数、浮点数的加、减、乘、除 字符运算 赋值运算 过程调用等 特点：尽管每种运
6、算的执行时间不同，但一般只花 一个固定量的时间（单位时间）就可完成。,2）计算的约定（续）,其他运算：字符串操作：与字符串中字符的数量成正比 记录操作：与记录的属性数、属性类型等有关 特点：运算时间无定量 如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。如：Tstring=Length（String）*tchar,3）工作数据集的选择编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。测试数据集的生成在目前算法证明与程序正确性证明没有取得理论上的突破性进展的情况下，是程序测试与算法分析中的关键技术之一。作为算法分析的数据集：典
7、型特征 作为程序性能测试的数据集：对执行指标产生影响的性质,3.如何进行算法分析？对算法进行全面分析，可分两个阶段进行：事前分析：就算法本身，通过对其执行性能的理论分析，得出关于算法特性时间和空间的一个特征 函数（、）与计算机物理软硬件没有 直接关系。事后测试：将算法编制成程序后实际放到计算机上运行，收集其执行时间和空间占用等统计资料，进行 分析判断直接与物理实现有关。,1）事前分析目的：试图得出关于算法执行特性的一种形式描 述，以“理论上”衡量算法的“好坏”。如何给出反映算法执行特性的描述？最直接方法：统计算法中各种运算的执行情况，包括：运用了哪些运算 每种运算被执行的次数 该种运算执行一次
8、所花费的时间等。算法的执行时间=Fi*ti,频率计数 例：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)：x x+y 执行了 1 次(b)：x x+y 执行了 n 次(c)：x x+y 执行了 n2 次 定义：频率计数：一条语句或一种运算在算法（或程序）体中的执行次数。,一条语句在整个程序运行时实际执行时间=频率计数*每执行一次该语句所需的时间 如何刻画算法执行特性的形式描述实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，
9、没有统一的描述模型。在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。,数量级 语句的数量级：语句的执行频率 例：1，n，n2 算法的数量级：算法所包含的所有语句的执 行频率之和。算法的数量级从本质上反映了一个算法的执行特性。例：假如求解同一个问题的三个算法分别具有n，n2，n3数量级。若n=10，则可能的执行时间将分别是10，100，1000个单 位时间与环境因素无关。,算法的输入规模,算法的执行时间随问题规模的增长而增长，增长的速度随不同的算法而不同没有一个方法可以准确的计算算法的具体执行时间 语言、编译系统、计算机实际上，在评估算法的性能时，并不需
10、要对算法的执行时间作出准确的统计，人们希望算法与实现的语言无关、与执行的计算机无关所关心的是：算法的执行时间，随着输入规模的增长而增长的情况,计算时间/频率计数的表示函数 通过事前分析给出算法计算时间（频率计数）的一个函数表示形式，一般记为与输入规模n有关的函数形式：f(n)空间特性分析UA(n)=算法在实例大小为n上运行时，所需要的内存单元数目处理器的特性如果算法在并行机上运行，则还需要考虑算法对处理器的需求。,2）事后测试目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论包括正确性、执行性能等，比较、优化所设计的算法。分析手段：作时、空性能分布图,4.计算时间的渐近表示,记：
11、算法的计算时间为f(n)数量级限界函数为g(n)其中，n是输入或输出规模的某种测度。f(n)表示算法的“实际”执行时间与机器及语言有关。g(n)是形式简单的函数，如nm，logn，2n，n!等。是事前分析中通过对计算时间或频率计数统计分析所得的、与机器及语言无关的函数。以下给出算法执行时间：上界（）、下界（）、“平均”（）的定义。,1）上界函数,定义1 如果存在两个正常数c和n0，对于所有的nn0，有|f(n)|c|g(n)|则记作f(n)=(g(n)含义：如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数
12、。f(n)的数量级就是g(n)。f(n)的增长最多像g(n)的增长那样快试图求出最小的g(n)，使得f(n)=(g(n)。,多项式定理:定理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|则，定理得证。,计算时间的数量级对算法有效性的影响 数量级的大小对算法的有效性有决定性的影响。例：假设解决
13、同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n2和nlogn。则，n=1024：分别需要 1048576 和 10240 次运算。n=2048：分别需要 4194304 和 22528 次运算。分析：在n加倍的情况下，一个(n2)的算法计算时间增长 4 倍，而一个(nlogn)算法则只用两倍多一点的时间即可完成。,算法分类（计算时间）,多项式时间算法：可用多项式（函数）对其计算时间限界的算法。常见的多项式限界函数有：(1)(logn)(n)(nlogn)(n2)(n3)指数时间算法：计算时间用指数函数限界的算法 常见的指数时间限界函数：(2n)(n！)(nn)说明：当n取值较
14、大时，指数时间算法和多项式时间 算法在计算时间上非常悬殊。,计算时间函数值比较,3,典型的计算时间函数曲线,当数据集的规模很大时，要在现有的计算机系统上运行具有比(nlogn)复杂度还高的算法是比较困难的。指数时间算法只有在n取值非常小时才实用。要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度，而不是（仅仅依靠）提高计算机的速度。,定义2.2 如果存在两个正常数c和n0，对于所有的nn0，有|f(n)|c|g(n)|则记作f(n)=(g(n)含义：如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n
15、)的一个下界函数。f(n)的增长至少像g(n)的增长那样快试图求出“最大”的g(n)，使得f(n)=(g(n)。,2）下界函数,定义1.3 如果存在正常数c1，c2和n0，对于所有的nn0，有 c1|g(n)|f(n)|c2|g(n)|则记作含义：算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作：既有f(n)=(g(n)，又有f(n)=(g(n)记号表明算法的运行时间有一个较准确的界,3）“平均情况”限界函数,4）限界函数的性质,1）若 且，则。即具有传递性。（同）2）当且仅当 3）若，则。即，定义了一个等价关系（等价类）,程序运行时间的计算,例1：简单的赋值语句 a=
16、b;该语句执行时间为一常量，为,例2：sum=0;for(i=1;i=n;i+)sum+=n;该语句执行时间为,例3 比较两个程序 sum1=0;for(i=1;i=n;i+)for(j=1;j=n;j+)sum1+;sum2=0;for(i=1;i=n;i+)for(j=1;j=i;j+)sum2+;,两个程序的执行时间都是 不过第二个程序的运行时间约为第一个的一半,2.3 关于SPARKS语言,本书为描述算法选用的一种类计算机语言类PASCAL语言结构化程序描述,1.基本语法成分,1）数据类型：整型、实型、布尔型、字符型2）变量声明：类型说明符 变量；integer i,j;boolean
17、 b;char c3）赋值运算：（变量）（表达式）4）逻辑运算：and or not5）关系运算：6）数组声明：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 vblestart to finish by increment do S repeat,2.同质异项3.其它 函数的定义与调用、函数和过程、
18、变量与形式参数,2.4 基本数据结构,1.栈和队列栈和队列：n个元素的线性表利用动态数据结构链表实现栈或队列利用静态数据结构数组实现栈或队列基于以上两种表示形式的栈和队列上的基本运算,栈的数组表示,用一维数组STACKS（1:n）表示栈底：STACKS（1）第i个元素STACKS(i)栈顶指针：top,procedure ADD(item,STACK,n,top)if top n then call STACKFULL endif top top+1 STACK(top)itemend add,procedure DELETE(item,STACK,top)if top 0 then call
19、 STACKEMPTY endif item STACK(top)top top-1end DELETE,栈的链接表表示,一种单向链接表两个信息段：DATA存放数据，LINK指向前一节点,节点插入 call GETNODE(T)DATA(T)item LINK(T)STACK STACK T,节点删除 item DATA(STACK)T STACK STACK LINK(SATCK)call RETNODE(T),A,STACK,0,2.树1）树的一般定义定义2.4 树（tree）是一个或多个结点的有限集合，它使得：有一个指定为根（root）的结点剩余结点被划分成m0个不相交的集合：T1，Tm
20、 这些集合的每一个又都是一棵树，并称T1，Tm为根的子树。,关于树的重要概念结点的度（degree）：一个结点的子树数树的度：树中结点度的最大值结点的级（level）（又叫层）：设根是1级，若某结点在p级，则它的儿子在p+1级树的高度（或深度）：树中结点的最大级数叶子（终端结点）：度为0的结点内结点（非终端结点）：度不为0的结点森林：m0个不相交树的集合。,树的表示方法：用链接表表示；每个结点三个信息段：TAG,DATA,LINK TAG0，DATA存数据；TAG=1,DATA存链接信息,2）二元树定义2.5 二元树（binary tree）是结点的有限集合，它或者为空，或者由一个根和两棵称为
21、左子树和右子树的不相交二元树所组成。二元树与度为2的树的区别二元树性质1：引理1.1 一棵二元树第 i级的最大结点数是2i-1。深度为k的二元树的最大结点数为2k-1,k0。,特殊形态的二元树 满二元树：深度为k且有2k-1个结点的二元树,完全二元树：一棵有n个结点深度为k的二元树，当它的结点相当于深度为k的满二元树中编号为1到n的结点时，称该二元树是完全的。完全二元树的叶子结点至多出现在相邻的两级上。完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理2.2）。,二元树的表示方法 1.数组表示法：对于完全二元树，空间效率好；其他二元树，要浪费大量空间 2.链表法：结构简单，有效。链表中
22、每个结点有三个信息段，LCHILD,DATA和RCHILD,堆：堆是一棵完全二元树，它的每个结点的值至少和该结点的儿子们（如果存在的话）的值一样大（max-堆）（或小，min-堆）。,二分检索树：二分检索树是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：的左子树的所有元素比根结点中的元素小；的右子树的所有元素比根结点中的元素大；的左子树和右子树也是二分检索树。注：二分检索树要求树中所有结点的元素值互异,3.图,图由称之为结点和边的两个集合组成，记为G=（V，E）。其中，是一个有限非空的结点集合；是结点对偶的集合，的每一对偶表示的一条边。,有关图的的重要概念,无向图
23、：边的表示（，）有向图：边的表示，成本：带有成本的图称为网络邻接：结点的度（出度入度）路径：由结点vp到vq的一条路（path）是结点 vp，vi1，vi2，vim，vq的一个序 列，它使得(vp，vi1)，(vi1，vi2)，(vim，vq)是E（G）的边。路的长度：组成路的边数。,简单路径：除了第一和最后一个结点可以相同以外，其它所有结点都不同。环：第一个和最后一个结点相同的简单路。连通图：在无向图中，如果每对结点之间都存在一条 路，则称该图是连通的。子图：是由G的结点集V的子集（记为VB）和边集E 中连接VB中结点的边的子集所组成的图。连通分图：一个图的最大连通子图。有向图的强连通性：在有向图中，如果对于每一对结 点i和j，既存在一条从i到j的路，又存在一条从j 到i的路，则称该有向图是强连通的。,图的表示方法,邻接矩阵 邻接表,
