《算法设计与分析基础.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析基础.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法设计算法设计与分析与分析 The The Design and Analysis of Algorithms2022/12/212022/12/211 1LingJie/GDUTLingJie/GDUT第第1章章 绪绪 论论主要内容：1.1 算法的概念 1.2 算法问题求解的基础 1.3 重要问题类型 1.4 基本数据结构2022/12/212022/12/212 2LingJie/GDUTLingJie/GDUT1.1 算法的概念1 1、算法概念、算法概念没有一个统一的严谨的定义。一般而言，对于计没有一个统一的严谨的定义。一般而言，对于计算机算法的概念是这样描述的：算法是在有限步算机算法
2、的概念是这样描述的：算法是在有限步骤内求解某一问题所使用的一组定义明确的指令。骤内求解某一问题所使用的一组定义明确的指令。本书采用的定义：本书采用的定义：An An algorithmalgorithm is a sequence of is a sequence of unambiguous instructions for solving a unambiguous instructions for solving a problem=problem=算法是求解某一问题所使用的一系列清算法是求解某一问题所使用的一系列清晰的指令。晰的指令。2022/12/212022/12/213 3Lin
3、gJie/GDUTLingJie/GDUT2、算法的概念图、算法的概念图注意：计算机发明以前也有算法问题问题算法算法“计算机计算机”输出输出输入输入2022/12/212022/12/214 4LingJie/GDUTLingJie/GDUT3、算法的三个要素、算法的三个要素 1).数据:运算序列中作为运算对象和结果的数据.2).运算:运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移:运算序列中的控制和转移.2022/12/212022/12/215 5LingJie/GDUTLingJie/GDUT4、算法的一般特征、算法的一般特征 1).1).有穷性有穷性 finiteness
4、finiteness 算法必须在执行有穷步后终止算法必须在执行有穷步后终止,且每一步均在有且每一步均在有限时间内完成限时间内完成 2).2).确定性确定性 definiteness definiteness 算法的每个步骤必须有明确的意义算法的每个步骤必须有明确的意义,对每种可能对每种可能的情况的情况,算法都要给出确定的操作算法都要给出确定的操作.3).3).能行性能行性effectivenesseffectiveness 算法中的每个步骤是能够实现的算法中的每个步骤是能够实现的,算法执行结果算法执行结果要达到预期目的要达到预期目的 4).4).有有0 0个或多个输入项个或多个输入项,至少有一
5、个输出项至少有一个输出项.2022/12/212022/12/216 6LingJie/GDUTLingJie/GDUT举例举例举例举例:计算最大公约数的欧几里德算法计算最大公约数的欧几里德算法计算最大公约数的欧几里德算法计算最大公约数的欧几里德算法ALGORITHM EuclidALGORITHM Euclid（mm，n n）/计算两个整数计算两个整数mm、n n的最大公约数的最大公约数gcdgcd（mm，n n）/输入：非负整数输入：非负整数mm，n n，其中，其中mm，n n不同时为零不同时为零/输出：输出：mm，n n的最大公约数的最大公约数while n 0 dowhile n 0
6、dor r m mod n m mod nmm n nn n r rreturn mreturn m2022/12/212022/12/217 7LingJie/GDUTLingJie/GDUT求求求求gcd(m,ngcd(m,n)的原理：的原理：的原理：的原理：（结构化的描述）（结构化的描述）第一步：如果第一步：如果n=0,n=0,返回返回mm的值作为结果，结束；否则进入的值作为结果，结束；否则进入 第二步。第二步。第二步：用第二步：用n n除除m,m,余数赋值给余数赋值给r r，进入第三步。，进入第三步。第三步：将第三步：将n n的值赋给的值赋给mm，将，将r r的值赋给的值赋给n n，返
7、回第一步。，返回第一步。例：例：gcd(60,24)=?gcd(60,24)=?1-1 1-1、m=60,n=24m=60,n=24 1-2 1-2、60 mod 24=12,r=12,60 mod 24=12,r=12,1-3 1-3、m=24,n=12m=24,n=12 2-1 2-1、24 mod 12=0,r=024 mod 12=0,r=0 2-2 2-2、m=12,n=0m=12,n=0 2-32-3、条件、条件“n=0”n=0”满足，返回满足，返回gcd(mgcd(m,n)=m=12,n)=m=122022/12/212022/12/218 8LingJie/GDUTLingJi
8、e/GDUT求求求求gcd(m,ngcd(m,n)的其他算法的其他算法的其他算法的其他算法算法二：连续整数检测法算法二：连续整数检测法第一步：将第一步：将minm,nminm,n 赋值给赋值给t t。第二步：第二步：mm除以除以t t，如果余数为，如果余数为0 0，进入第三步，否则进入第四步。，进入第三步，否则进入第四步。第三步：第三步：n n除以除以t t，如果余数为，如果余数为0 0，返回，返回t t的值；否则进入第四步。的值；否则进入第四步。第四步：把第四步：把t t的值减的值减1 1，返回第三步。，返回第三步。例：例：gcd(60,24)gcd(60,24)t=min60,24=24,
9、m=60,n=24t=min60,24=24,m=60,n=24 60mod24=120,60mod24=120,t=23,24 mod 23=1 0t=23,24 mod 23=1 0t=22,24 mod 22=2 0t=22,24 mod 22=2 0t=21,24 mod 21=3 0t=21,24 mod 21=3 0.t=12,24 mod 12=0,t=12,24 mod 12=0,返回返回gcd(mgcd(m,n)=t=12,n)=t=122022/12/212022/12/219 9LingJie/GDUTLingJie/GDUT算法三：质因数分解法算法三：质因数分解法第一步
10、：找出第一步：找出mm的所有质因数。的所有质因数。第二步：找出第二步：找出n n的所有质因数。的所有质因数。第三步：从第一步求得的第三步：从第一步求得的mm的质因数分解式和第二步求得的的质因数分解式和第二步求得的n n 的质因数分解式中，找出所有公因数。的质因数分解式中，找出所有公因数。第四步：将第三步找到的公因数相乘，结果为所求的第四步：将第三步找到的公因数相乘，结果为所求的 gcd(m,ngcd(m,n)例：例：m=60=m=60=22322355 n=24=2 n=24=2223223 公因数为公因数为 223223 结果为结果为 gcd(m,ngcd(m,n)=12)=12存在问题：如
11、何求所有的质因数存在问题：如何求所有的质因数/素因子？素因子？2022/12/212022/12/211010LingJie/GDUTLingJie/GDUT求连续素数序列的筛法求连续素数序列的筛法求连续素数序列的筛法求连续素数序列的筛法-2 23 34 45 56 67 78 89 910101111 12121313141415151616 17171818191920202121 2222232324242525问题：问题：求不大于n=25的质数 序列。筛法：1、取 p=2，消去p的倍数。2、取 p=3，消去p的倍数。直至 p=?结束2022/12/212022/12/211111Lin
12、gJie/GDUTLingJie/GDUT-2*2*3 34 45 56 67 78 89 91010111112121313141415151616171718181919202021212222232324242525-2 23*3*5 57 79 911111313151517171919212123232525-2 23 35*5*7 7111113131717191923232525-2 23 35 57 7111113131717191923232022/12/212022/12/211212LingJie/GDUTLingJie/GDUT求连续素数序列的筛法求连续素数序列的筛法求
13、连续素数序列的筛法求连续素数序列的筛法Sieve(nSieve(n)For p=2 to n do /For p=2 to n do /设立数组设立数组A2AnA2An ApAp=p=pFor p=2 to do /For p=2 to do /if Ap0,j=p*p if Ap0,j=p*p while j=n do while j=n do AjAj=0=0 j=j=j+pj+pi=0 /i=0 /将将A A中剩余的元素复制到数组中剩余的元素复制到数组L L供连续输出供连续输出For p=2 to n doFor p=2 to n do if Ap0,if Ap0,LiLi=ApAp i
14、=i+1 i=i+1Return L Return L 2022/12/212022/12/211313LingJie/GDUTLingJie/GDUT5、算法的分类、算法的分类从解法上分：从解法上分：优化算法优化算法:算法中的基本运算为逻辑运算。算法中的基本运算为逻辑运算。数值算法数值算法:算法中的基本运算为算术运算。算法中的基本运算为算术运算。从处理方式上分：从处理方式上分：串行算法串行算法:串行计算机上执行的算法。串行计算机上执行的算法。并行算法并行算法:并行计算机上执行的算法。并行计算机上执行的算法。2022/12/212022/12/211414LingJie/GDUTLingJie
15、/GDUT1.2 算法问题求解基础 观点观点:算法是问题的程序化解决方案算法是问题的程序化解决方案 算法设计与分析过程的典型步骤算法设计与分析过程的典型步骤:1 1、了解问题的内容、了解问题的内容 2 2、了解计算设备的性能、了解计算设备的性能 3 3、在精确解法和近似解法之间选择、在精确解法和近似解法之间选择 4 4、确定适当的数据结构、确定适当的数据结构 5 5、算法设计技术、算法设计技术 6 6、详细表述算法的方法、详细表述算法的方法 7 7、证明算法的正确性、证明算法的正确性 8 8、分析算法、分析算法 9 9、为算法写代码、为算法写代码2022/12/212022/12/211515
16、LingJie/GDUTLingJie/GDUT图图1.2 1.2 算法设计与分析的过程算法设计与分析的过程2022/12/212022/12/211616LingJie/GDUTLingJie/GDUT1.2.1 了解问题的内容当遇到一个问题时，首先要清楚这个问题的所当遇到一个问题时，首先要清楚这个问题的所有内容。如果这个问题已经给出了明显的要求，有内容。如果这个问题已经给出了明显的要求，如对成绩排序，那么只需要看看它是属于那一如对成绩排序，那么只需要看看它是属于那一类的问题，然后参考相关的资料。类的问题，然后参考相关的资料。了解问题内容这个步骤是十分重要的，因为只了解问题内容这个步骤是十分
17、重要的，因为只有知道了问题具有什么样的输入，需要得到什有知道了问题具有什么样的输入，需要得到什么样的输出，问题的解决才可能进行下去。理么样的输出，问题的解决才可能进行下去。理解了问题是问题求解的关键。解了问题是问题求解的关键。2022/12/212022/12/211717LingJie/GDUTLingJie/GDUT1.2.2 了解计算设备的能力 在清楚了解了问题的内容之后，下一步是确定在清楚了解了问题的内容之后，下一步是确定用于解决问题的设备的能力。目前一般使用的用于解决问题的设备的能力。目前一般使用的计算机都是冯诺依曼（计算机都是冯诺依曼（von Neumannvon Neumann）
18、体系架）体系架构的。它的一个最重要假设是，程序指令的执构的。它的一个最重要假设是，程序指令的执行是顺序的。针对这一类计算机设计的算法被行是顺序的。针对这一类计算机设计的算法被称为串行算法（称为串行算法（sequential algorithmssequential algorithms）。与）。与之相区别的是所谓的并行计算机以及并行算法之相区别的是所谓的并行计算机以及并行算法（parallel algorithmsparallel algorithms）。指令能够并行的执行，）。指令能够并行的执行，效率当然会大大提高，额外需要考虑的则是指效率当然会大大提高，额外需要考虑的则是指令执行顺序以及同
19、步等问题。并行算法的设计令执行顺序以及同步等问题。并行算法的设计有相应的理论，这里仅考虑串行算法。有相应的理论，这里仅考虑串行算法。2022/12/212022/12/211818LingJie/GDUTLingJie/GDUT1.2.3 选择精确或者近似的算法 解决问题下一步要考虑的是使用精确的还是近解决问题下一步要考虑的是使用精确的还是近似的算法。并不是每一个可解的问题都有精确似的算法。并不是每一个可解的问题都有精确的算法，例如求一个数的平方根，求非线性方的算法，例如求一个数的平方根，求非线性方程的解等。有时候一个问题有精确的解法但是程的解等。有时候一个问题有精确的解法但是算法的执行效率很
20、差，例如旅行家问题。因此算法的执行效率很差，例如旅行家问题。因此如果待处理的问题涉及到上述那些方面，则要如果待处理的问题涉及到上述那些方面，则要考虑是选择精确的还是近似的算法。考虑是选择精确的还是近似的算法。2022/12/212022/12/211919LingJie/GDUTLingJie/GDUT1.2.4 确定合适的数据结构 许多程序设计的教程都提到：程序设计算法许多程序设计的教程都提到：程序设计算法数据结构（数据结构（Programs=Algorithms+Data Programs=Algorithms+Data StructuresStructures），由此可以看出数据结构对算
21、法），由此可以看出数据结构对算法的重要性。例如在处理搜索问题时，对于仅仅的重要性。例如在处理搜索问题时，对于仅仅进行搜索的算法只需要用到简单的数组即可，进行搜索的算法只需要用到简单的数组即可，如果搜索后伴随着插入删除操作时，那么用链如果搜索后伴随着插入删除操作时，那么用链表以及堆等复杂的数据结构的算法更加可取。表以及堆等复杂的数据结构的算法更加可取。2022/12/212022/12/212020LingJie/GDUTLingJie/GDUT1.2.5 选择算法设计技术 算法设计技术（算法设计技术（algorithm design techniquealgorithm design tech
22、nique）或者算法设计策略（或者算法设计策略（strategystrategy）指的是解决一）指的是解决一系列不同问题的通用设计思想。常用的设计技系列不同问题的通用设计思想。常用的设计技术包括分治法（术包括分治法（Divide and ConquerDivide and Conquer），贪婪），贪婪法（法（Greedy TechniqueGreedy Technique），动态规划），动态规划（Dynamic ProgrammingDynamic Programming），回溯法），回溯法（BacktrackingBacktracking），分支限定法（），分支限定法（Branch and
23、 Branch and BoundBound）等。）等。2022/12/212022/12/212121LingJie/GDUTLingJie/GDUT1.2.6 详细表述该算法的方法 可以用到的工具有自然语言（可以用到的工具有自然语言（nature nature languagelanguage）、伪代码（）、伪代码（pseudocodepseudocode）以及程序）以及程序流程图（流程图（flow chartflow chart）等。）等。当对一个问题有了概要的理解后，下面的工作当对一个问题有了概要的理解后，下面的工作就是把这个问题的想法进行细化。所谓的细化就是把这个问题的想法进行细化。
24、所谓的细化就是把它们表示成算法的步骤。就是把它们表示成算法的步骤。2022/12/212022/12/212222LingJie/GDUTLingJie/GDUT1.2.7 确认算法的正确性 当给算法一个合法输入，而该算法给出一个错当给算法一个合法输入，而该算法给出一个错误的结果时，可以证明这个算法是错误的。但误的结果时，可以证明这个算法是错误的。但如果证明一个算法是正确，情况就不是那样地如果证明一个算法是正确，情况就不是那样地简单。算法的测试有一套完整的理论，这里不简单。算法的测试有一套完整的理论，这里不作详细叙述。作详细叙述。特别需要提出的是，所谓算法的正确性指的是：特别需要提出的是，所谓
25、算法的正确性指的是：对于任意合法的输入在有限时间内都能得到正对于任意合法的输入在有限时间内都能得到正确的结果。如果算法是一个近似算法，那么正确的结果。如果算法是一个近似算法，那么正确性则是指输出结果与理论结果之间的误差在确性则是指输出结果与理论结果之间的误差在一个可以接受的范围内。一个可以接受的范围内。2022/12/212022/12/212323LingJie/GDUTLingJie/GDUT1.2.8 对算法的分析 时空的观点时空的观点 发展的观点：算法的适应性（发展的观点：算法的适应性（generalitygenerality）最强）最强 设计的观点：算法的设计时间最少设计的观点：算法
26、的设计时间最少 交流的观点：算法最容易理解（交流的观点：算法最容易理解（simplicitysimplicity）2022/12/212022/12/212424LingJie/GDUTLingJie/GDUT1.2.9 为算法写代码目前而言，大部分的算法最后还是需要通过程目前而言，大部分的算法最后还是需要通过程序语言进行实现。针对不同的问题，还需要考序语言进行实现。针对不同的问题，还需要考虑什么样的程序语言才是最适合的，这与个人虑什么样的程序语言才是最适合的，这与个人的知识组成以及程序语言本身的特性等有关。的知识组成以及程序语言本身的特性等有关。部分的程序语言可能需要对算法进行修改以适部分的
27、程序语言可能需要对算法进行修改以适应这种语言本身。例如广泛用于科学计算的应这种语言本身。例如广泛用于科学计算的MatlabMatlab语言，它是基于矩阵的语言，提供了大语言，它是基于矩阵的语言，提供了大量数值计算的函数，然而它的循环计算能力相量数值计算的函数，然而它的循环计算能力相对较弱，所以如果把算法中涉及循环的过程通对较弱，所以如果把算法中涉及循环的过程通过向量的形式进行，那么最终的效率将能得到过向量的形式进行，那么最终的效率将能得到很大的提高。很大的提高。2022/12/212022/12/212525LingJie/GDUTLingJie/GDUT1.3 重要问题的类型排序问题（排序问
28、题（SortingSorting）查找查找/搜索问题（搜索问题（SearchingSearching）串处理问题（串处理问题（String problemsString problems）图论问题（图论问题（Graph problemsGraph problems）组合问题（组合问题（Combinatorial problemsCombinatorial problems）几何问题（几何问题（Geometric problemsGeometric problems）数值计算问题（数值计算问题（Numerical problemsNumerical problems）加密问题（加密问题（Encr
29、pytionEncrpytion problems problems）2022/12/212022/12/212626LingJie/GDUTLingJie/GDUT1.3.1 排序问题 所谓的所谓的“排序排序”就是把一组杂乱的数据按照一就是把一组杂乱的数据按照一定的规律顺次排列起来。排序是很重要的，因定的规律顺次排列起来。排序是很重要的，因为它可以使得以后的工作更加地容易。目前，为它可以使得以后的工作更加地容易。目前，计算机科学家发明了很多的排序算法，然而这计算机科学家发明了很多的排序算法，然而这些排序算法中并不存在一种算法是绝对最优的。些排序算法中并不存在一种算法是绝对最优的。这里介绍几个
30、与这里介绍几个与“排序排序”相关的重要概念：数相关的重要概念：数据表据表 、关键字、关键字 、主关键字、主关键字 、排序的稳定性、排序的稳定性 、内排序与外排序内排序与外排序 。2022/12/212022/12/212727LingJie/GDUTLingJie/GDUT1.3.2 查找/搜索问题 所所谓谓查查找找/搜搜索索，就就是是在在数数据据集集合合中中寻寻找找满满足足某某种种条条件件的的数数据据对对象象。一一般般的的形形式式是是先先给给出出一一个个特特定定值值，然然后后在在数数据据集集合合中中找找出出关关键键字字等等于于该该特特定定值值的的对对象象。对对于于搜搜索索问问题题，通通常常需
31、需要要返返回回的的结结果果可可能能有有两两种种。一一种种是是简简单单的的搜搜索索成成功功或或者者失失败败的的信信息息；另另一一种种是是返返回回满满足足搜搜索索条条件件的的对象所在位置，如果找不到则返回不存在信息。对象所在位置，如果找不到则返回不存在信息。2022/12/212022/12/212828LingJie/GDUTLingJie/GDUT1.3.3 串处理问题 对对于于字字符符串串处处理理的的问问题题，这这里里只只是是对对其其中中一一类类特特殊殊的的问问题题进进行行讨讨论论，即即字字符符串串模模式式匹匹配配问问题题（string string matchingmatching）。问问
32、题题是是这这样样表表述述的的：在在一一篇篇文文章章或或文文章章的的一一部部分分中中找找出出单单词词第第一一次次出出现现的的位位置置。本本书书把把字字符符串串匹匹配配问问题题作作为为一一种种特特殊殊的的搜搜索索问问题题考考虑虑，因因为为两两者者是是有有相相似似之之处处的的。最最大大的的区区别别在在于于，一一般般搜搜索索问问题题是是单单一一的的关关键键字字的的搜搜索索，而而字字符符串串匹匹配配可可以以看看作作是是几几个个关关键键字字组组成成一一种种模模式式的的搜搜索索过过程程，因因此此对对模模式式的的分分析有助于算法效率的提高。析有助于算法效率的提高。2022/12/212022/12/21292
33、9LingJie/GDUTLingJie/GDUT1.3.4 图论问题 图论问题主要是与图或树相关的问题。这里所图论问题主要是与图或树相关的问题。这里所谓的谓的“图图”指的是一些顶点（指的是一些顶点（VertexVertex）与边）与边（EdgeEdge）的集合。图有着非常重要与丰富的实）的集合。图有着非常重要与丰富的实际应用，如通信网络，交通网络，工程计划等。际应用，如通信网络，交通网络，工程计划等。本书所涉及到的图论问题主要包括了图的遍历本书所涉及到的图论问题主要包括了图的遍历问题（问题（Graph TraversalGraph Traversal），最短路径问题以及），最短路径问题以及图
34、的特例图的特例树结构的排序、搜索中的应用问树结构的排序、搜索中的应用问题。题。2022/12/212022/12/213030LingJie/GDUTLingJie/GDUT1.3.5 组合问题现代的组合数学所涉及的领域更加广阔，其中现代的组合数学所涉及的领域更加广阔，其中的问题出自抽象代数、拓扑学、数学基础、图的问题出自抽象代数、拓扑学、数学基础、图论、博弈论、线性规划以及其他许多领域。值论、博弈论、线性规划以及其他许多领域。值得注意的是，这些来源不同的问题不能在一个得注意的是，这些来源不同的问题不能在一个统一的理论体系中得到有效的解决，而且随着统一的理论体系中得到有效的解决，而且随着问题的
35、输入量的增加，问题的规模急剧增长至问题的输入量的增加，问题的规模急剧增长至计算机的处理能力的极限，所以可以说组合数计算机的处理能力的极限，所以可以说组合数学问题是最难的一类问题。学问题是最难的一类问题。2022/12/212022/12/213131LingJie/GDUTLingJie/GDUT1.3.6 几何问题几何问题是几何数学上与点、线、多边形相关几何问题是几何数学上与点、线、多边形相关的问题。当然，这不是一本几何学的书，所以的问题。当然，这不是一本几何学的书，所以这里只会涉及如直线段的表示、相交判断等基这里只会涉及如直线段的表示、相交判断等基本问题。同时还会给出最近邻点问题与凸包问本
36、问题。同时还会给出最近邻点问题与凸包问题这两个重要问题的介绍。它们都有穷举法与题这两个重要问题的介绍。它们都有穷举法与分治法的算法版本，通过比较，可以深入体会分治法的算法版本，通过比较，可以深入体会到其中所用到的算法设计思想。到其中所用到的算法设计思想。2022/12/212022/12/213232LingJie/GDUTLingJie/GDUT1.3.7 数值问题 数值计算问题是另一大类问题，它要解决的问数值计算问题是另一大类问题，它要解决的问题包括：求解方程或者方程组，求数值积分等。题包括：求解方程或者方程组，求数值积分等。这些问题常常只能给出一个近似的结果，而不这些问题常常只能给出一个近似的结果，而不是精确的解析解。并且这些问题常涉及到具体是精确的解析解。并且这些问题常涉及到具体的数据，由于计算机对数字表示的精度问题，的数据，由于计算机对数字表示的精度问题，所以还需要考虑可能带来的误差以及这些误差所以还需要考虑可能带来的误差以及这些误差对算法稳定性的影响。对算法稳定性的影响。2022/12/212022/12/213333LingJie/GDUTLingJie/GDUT