算法设计与分析 王红梅 第二版 第1章 算法设计基础.ppt

1、第1章 算法绪论Algorithm Introduction,海南大学信息科学技术学院 College of Information Science and Technology, Hainan University,算法设计与分析本科生课程 Design and Analysis of Algorithm,第1章 算法绪论,1.1算法的基本概念 1.2为什么要学习和研究算法 1.3 重要的问题类型,2020/9/10,Algorithm Introduction,2,算法理论的两大论题： 1. 算法设计（解决问题） 2. 算法分析（评价，改进） 本章主要知识点：,1.1算法的基本概念,算法及

2、其重要特性 算法的描述方法 算法设计的一般过程,2020/9/10,Algorithm Introduction,3,算法及其重要特性,算法（Algorithm）? 定义1.1 算法是解某一特定问题的一组有穷规则的集合。 即，对特定问题求解步骤的一种描述，是指令的有限序列，有以下五大特性： 输 入：一个算法有零个或多个外部量作为算法的输入。 输 出：一个算法会产生至少一个量作为输出。 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 可行性：算法描述的操作可以通过已经实现的基本操作执行有限

3、次来实现。,2020/9/10,Algorithm Introduction,4,算法及其重要特性,例1.1 求两个自然数的最大公约数（直观的方法） 第1步：找出m的所有质因子； 第2步：找出n的所有质因子； 第3步：从第上述两步所得到的质因子中找出所有公因子； 第4步：将所有公因子相乘，即为m和n的最大公约数,2020/9/10,Algorithm Introduction,5,这是算法吗？ 为什么？,算法及其重要特性,程序? 是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(3)，即有穷性。 “好算法”的重要特性： （1）正确性：合法的输入，都会得出正确的结果 （2）健壮性：非

4、法的输入，应能识别并处理 （3）可理解性：可读性，易理解 （4）抽象分级：通过抽象分级减少求解步骤 （5）高效性：时间和空间效率,2020/9/10,Algorithm Introduction,6,1.1算法的基本概念,算法及其重要特性 算法的描述方法 算法设计的一般过程 重要的问题类型,2020/9/10,Algorithm Introduction,7,算法的描述方法,2020/9/10,Algorithm Introduction,8,为了清楚准确地将算法求解的步骤记录下来，必须要描述算法，常用的方法：自然语言、流程图、程序设计语言和伪代码等 自然语言 优点：容易理解 缺点：冗长、二义

5、性、过于抽象难于转换为程序 使用方法：粗线条描述算法思想 注意事项：避免写成自然段,算法的描述方法,2020/9/10,Algorithm Introduction,9, 输入m 和n； 求m除以n的余数r； 若r等于0，则n为最大公约数，算法结束； 否则执行第步； 将n的值放在m中，将r的值放在n中； 重新执行第步。,欧几里德算法(自然语言描述),算法的描述方法,2020/9/10,Algorithm Introduction,10, 流程图 优点：流程直观 缺点：严密性不及程序设计语言、灵活性不如自然语言 使用方法：描述简单算法 注意事项：注意抽象层次,算法的描述方法,2020/9/10,

6、Algorithm Introduction,11,欧几里德算法流程图,算法的描述方法,2020/9/10,Algorithm Introduction,12, 程序设计语言 优点：能由计算机执行 缺点：抽象性差，对语言要求高 使用方法：算法需要验证 注意事项：将算法写成子函数,算法的描述方法,2020/9/10,Algorithm Introduction,13,#include int CommonFactor (int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return m; void main( ) coutCom

7、monFactor(63, 54)endl; ,欧几里德算法,算法的描述方法,2020/9/10,Algorithm Introduction,14, 伪代码算法语言 伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法、操作指令，再结合自然语言来设计。 优点：表达能力强，抽象性强，容易理解 使用方法：算法语言,算法的描述方法,2020/9/10,Algorithm Introduction,15,欧几里德算法（C+语法的伪代码表达）,1. r = m % n; 2. 循环直到 r 等于0 2.1 m = n; 2.2 n = r; 2.3 r

8、 = m % n; 3. 输出 n ;,1.1算法的基本概念,为什么要学习算法 算法及其重要特性 算法的描述方法 算法设计的一般过程 重要的问题类型,2020/9/10,Algorithm Introduction,16,算法设计的一般过程,2020/9/10,Algorithm Introduction,17,1理解问题（输入、目标、输出以及用适当的数据结构来描述，在精确解和近似解间做选择）2. 选择算法设计技术（蛮力法、分治法等） 3设计并描述算法 4手工运行跟踪算法 （发现逻辑错误） 5分析算法的效率（时间和空间效率） 6实现算法 （根据算法编写代码）,1.2为什么要学习和研究算法,算法

9、在问题求解中的地位 算法训练能够提高计算思维能力 算法研究是推动计算机技术发展的关键,2020/9/10,Algorithm Introduction,18,算法在问题求解中的地位,程序是蓝色的诗，算法是程序的灵魂 问题的求解过程： 分析问题设计算法编写程序整理结果 程序设计研究的四个层次： 算法方法学语言工具,2020/9/10,Algorithm Introduction,19,算法在问题求解中的地位,相同问题不同的解决方案产生不同的算法，不同的算法设计出不同的程序，程序的解题思路、复杂程序、效率也不相同。 例1.2 求两个自然数的最大公约数 想法1用短除法找出两个数的公因子，再相乘就是最

10、大公约数。 算法1找两个数的公因子目前只能用蛮力法逐个尝试，用2min(m,n)进行枚举尝试。,2020/9/10,Algorithm Introduction,20,算法在问题求解中的地位,算法1.1：CommFactorl（伪代码） 输入：两个自然数m和n 输出：m和n的最大公约数 1. factor=1; 2. 循环变量i从2min(m,n),执行下述操作； 2.1 如果i是m和n的公因子，则执行下述操作； 2.1.1 factor=factor*i; 2.1.2 m=m/i ;n=n/i; 2.2 如果i不是m和n的公因子，则i=i+1; 3. 输出factor;,2020/9/10,

11、Algorithm Introduction,21,算法在问题求解中的地位,int CommFactorl(int m, int n) int i,factor=1; for(i=2; i=m ,2020/9/10,Algorithm Introduction,22,算法在问题求解中的地位,想法2欧几里得算法效率更高。将两个数辗转相除直到余数为0。 算法2欧几里得算法的伪代码描述。 算法1.2 CommFactor2 输入：两个自然数m和n 输出：m和n的最大公约数 1. r = m % n; 2. 循环直到 r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n;

12、 3. 输出 n ;,2020/9/10,Algorithm Introduction,23,算法在问题求解中的地位,算法实现2欧几里得算法的C+语言描述。 int CommonFactor (int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return m; ,2020/9/10,Algorithm Introduction,24,算法在问题求解中的地位,算法比较 算法1的时间主要耗费在求余操作m%i=0&n%i=0 算法2的时间主要耗费在求余操作r=m % n 但两者求余运算次数差别较大，如以求48和36最大公约数为例，

13、算法1要进行10次求余，算法2只需两次求余。 光写出一个可以正确运行的算法还不够，特别是规模较大的数据上运行的算法，效率就成为一个重要的问题。,2020/9/10,Algorithm Introduction,25,算法训练能够提高计算思维能力,ACM/IEEECS提交的CC2005将计算机专业的基本学科能力归纳为：计算思维能力、算法设计与分析能力、程序设计与实现能力和系统能力。 计算思维主要包括形式化、模型化、抽象思维与逻辑思维，可以从算法的角度来看，计算思维就是将人的想法抽象为算法，算法设计过程是计算思维的具体运用。 算法训练就像一种思维体操，锻炼我们的思维。,2020/9/10,Algo

14、rithm Introduction,26,算法研究是推动计算机技术发展的关键,现代计算机在计算能力和存储容量上的革命，并不会终结算法的研究，因为现实世界的复杂性远远超出计算机技术的运算能力，光靠硬件，没有“好”的算法，是难于想像的。,2020/9/10,Algorithm Introduction,27,2020/9/10,Algorithm Introduction,28,1.3 重要的问题类型,1. 查找问题 2. 排序问题 3. 图问题 4. 组合问题 5. 几何问题,2020/9/10,Algorithm Introduction,29,1.3 重要的问题类型,查找问题 在一个数据集

15、合中查找满足给定条件的记录。 没有十全十美的查找算法 搜索引擎,2020/9/10,Algorithm Introduction,30,1.3 重要的问题类型,2. 排序问题 将一个记录的无序序列调整为一个有序序列的过程。 排序的主要目的是为了快速查找。 同样没有十全十美的排序算法,2020/9/10,Algorithm Introduction,31,1.3 重要的问题类型,3. 图问题 最古老最令人感兴趣。很多纷乱复杂的现实问题抽象出的数据模型都是图结构，如分子结构、排课问题、任务分配等。,TSP（Traveling Saleman Problem）问题：旅行n城市回到起点，每个城市只经历一次且总路程最短。,10城市 180000个可能解 20城市 6*1016个可能解 50城市 1062个可能解,2020/9/10,Algorithm Introduction,32,1.3 重要的问题类型,4. 组合问题 一般都是最优化问题，即寻找一个组合对象，能够满足特定的约束条件并使得某个目标函数取得极值。,组合问题算是计算领域最难解的问题，因为： （1）随着问题规模增大，组合对象数量极快增长（爆炸） （2）绝大多数组合问题尚未找到有效算法在可接受的时间内得到正确的解。,0/1背包问题：给定n个重量为w1, w2, ,wn、价值为v1, v2,