算法分析概述

1、1算法设计与分析算法设计与分析2学习要求学习要求n1 考勤考勤(五次五次缺勤，取消考试资格缺勤，取消考试资格)n2 作业作业(严禁抄袭，严禁抄袭，两次两次取消考试资格取消考试资格)n3 课堂纪律课堂纪律n4 课堂提问三次不回答，算缺勤一次，此后每课堂提问三次不回答，算缺勤一次，此后每一次不回答，则计一次缺勤。一次不回答，则计一次缺勤。n5 迟到迟到3次次算缺勤算缺勤n6 平时平时20%，考试，考试80%n7 严禁考试成绩出来后要求修改成绩严禁考试成绩出来后要求修改成绩3n本门课程课时少本门课程课时少n注重介绍思想注重介绍思想n不考虑算法的实现细节不考虑算法的实现细节n每个算法均可上机实现每个算

2、法均可上机实现n3节上机课节上机课课程特点课程特点4存在的疑问存在的疑问n什么是算法什么是算法n算法设计的整体过程算法设计的整体过程n为什么要引入算法为什么要引入算法(为什么要进行算法设计为什么要进行算法设计)n算法分析要涉及那些方面算法分析要涉及那些方面n（第二章内容）（第二章内容）5思考题n假设有四种类型的硬币，它们的面值分假设有四种类型的硬币，它们的面值分别为别为2角角5分，分，1角，角，5分和分和1分。现在要分。现在要找给某顾客找给某顾客6角角3分钱，如何找？（假设分钱，如何找？（假设各种类型的硬币足够多）各种类型的硬币足够多）6n四种类型的硬币，它们的面值分别为四种类型的硬币，它们的

3、面值分别为2角角5分分，1角，角，5分和分和1分分。现在要找给某顾客。现在要找给某顾客6角角3分分钱，钱，如何找？（假设各种类型的硬币足够多）如何找？（假设各种类型的硬币足够多）n拿出拿出2个个2角角5分的硬币，分的硬币，1个个1角，角，3个个1分分n拿出拿出6个个1角钱角钱 ， 3个个1分钱分钱n第一种方法的考虑：第一种方法的考虑：n首先选出一个面值不超过首先选出一个面值不超过6 6角角3 3分钱的最大硬币，既分钱的最大硬币，既2 2角角5 5分钱；分钱；n然后从然后从6 6角角3 3分中减去分中减去2 2角角5 5分，剩下分，剩下3 3角角8 8分；分；n再选出一个面值不超过再选出一个面值

4、不超过3 3角角8 8分的最大硬币，既又一个分的最大硬币，既又一个2 2角角5 5分，如此一直做下去。分，如此一直做下去。n每次挑选的硬币都是面值不超过找钱余额的最大硬币。每次挑选的硬币都是面值不超过找钱余额的最大硬币。n 第二种方法的考虑：按照钱的单位来找第二种方法的考虑：按照钱的单位来找。 7n结论结论n对于一个问题我们都有相应的解决方法对于一个问题我们都有相应的解决方法n一个问题有不同的方法一个问题有不同的方法n各方法有不同的特点各方法有不同的特点n方法一的方法一的找币数量找币数量少于方法二（少于方法二（6个个 VS 9个）个）n方法二简单方法二简单n有助于理解前面提出的问题有助于理解前

5、面提出的问题n什么是算法解决问题的方法什么是算法解决问题的方法n算法设计找出方法算法设计找出方法n算法分析分析方法的特点，选择合适方法算法分析分析方法的特点，选择合适方法8一 什么是算法概念n算法是一系列解决问题的算法是一系列解决问题的清晰指令清晰指令，也就，也就是说，能够对符合一定是说，能够对符合一定规范规范的的输入输入，在，在有有限时间限时间内获得所要求的内获得所要求的输出输出。 n简单的说简单的说，就是解决问题的一种方法或过就是解决问题的一种方法或过程。程。9一 什么是算法特征（1）确定性）确定性n 算法的每一个步骤都必须清晰，明确，这是来不得半点算法的每一个步骤都必须清晰，明确，这是来

6、不得半点含糊的。含糊的。n算法所处理的输入的值域必须仔细定义。算法所处理的输入的值域必须仔细定义。（2）多样性）多样性n算法的描述形式有多种。算法的描述形式有多种。n可能存在解决同一问题的多种算法。可能存在解决同一问题的多种算法。n针对同一个问题的算法可能会基于完全不同的解题思路，针对同一个问题的算法可能会基于完全不同的解题思路，而且解题目速度也会有显著不同。而且解题目速度也会有显著不同。（3）有穷性）有穷性：指令是有限的，每条指令的执行包含有限的：指令是有限的，每条指令的执行包含有限的工作量，算法的整个指令序列的执行会在有限时间内结工作量，算法的整个指令序列的执行会在有限时间内结束；束； （

7、4）输出）输出：一个算法有一个或多个输出，以反映对输入数：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；据加工后的结果。没有输出的算法是毫无意义的； 10二 算法设计分析过程证明正确性证明正确性分析算法分析算法设计程序设计程序理解问题理解问题精确解或近似解精确解或近似解选择数据结构选择数据结构算法设计策略算法设计策略设计算法设计算法11二 算法设计分析过程理解问题n问题问题: 一个一般化的概念一个一般化的概念. 例如例如: 排序问题排序问题n实例实例: 问题的一个实际情况问题的一个实际情况. n例如例如, 排排序问题中待排序的量的个数、每个量序问题中待排序

8、的量的个数、每个量的值构成了问题的一个实例。的值构成了问题的一个实例。 n算法为问题而建立，但是算法不能为问题算法为问题而建立，但是算法不能为问题而运行；而运行；n算法只能为问题的实例而运行。算法只能为问题的实例而运行。 n不要对算法解题的第一步敷衍了事，否则不要对算法解题的第一步敷衍了事，否则就要冒返工的风险就要冒返工的风险12二二 算法设计分析过程理解问题算法设计分析过程理解问题n任务任务n1）透彻地理解需求分析（目标与功能）；）透彻地理解需求分析（目标与功能）；对问题进行详细的定义（包括清晰的处理对问题进行详细的定义（包括清晰的处理步骤和输入的值域范围）。步骤和输入的值域范围）。n2）确

9、定问题类型。）确定问题类型。n3）考虑可采用的算法。）考虑可采用的算法。13n最重要的问题类型：最重要的问题类型：n 排序排序n查找查找n串处理串处理n图问题图问题n组合问题组合问题n几何问题几何问题n数值问题数值问题二二 算法设计分析过程理解问题算法设计分析过程理解问题14n是否支持并行计算。是否支持并行计算。n计算速度。计算速度。n内存容量内存容量。二二 算法设计分析过程算法设计分析过程计算设备的性能计算设备的性能15n近似解法的适合情况近似解法的适合情况n 1）存在精确解，但在可接受的时间内，）存在精确解，但在可接受的时间内，无法实现。无法实现。n 2）问题本身不存在精确解）问题本身不存

10、在精确解n 3）一个近似算法是某个精确求解方案的）一个近似算法是某个精确求解方案的一部分。一部分。n 二二 算法设计分析过程算法设计分析过程 精确解法或近似解法的抉择精确解法或近似解法的抉择16n算法数据结构程序算法数据结构程序n1）有些问题必须使用精心设计的数据结构才）有些问题必须使用精心设计的数据结构才能求解。能求解。n 2）算法与数据结构相互依存。）算法与数据结构相互依存。n学过哪些数据结构？学过哪些数据结构？n线性线性n图图n树树n集合与字典集合与字典二二 算法设计分析过程算法设计分析过程 确定适当的数据结构确定适当的数据结构17n穷举法（蛮力法）、分治法、动态规划、穷举法（蛮力法）、

11、分治法、动态规划、贪心法、回朔法等。贪心法、回朔法等。二二 算法设计分析过程算法设计分析过程 算法设计技术算法设计技术18n伪代码伪代码n 流程图流程图二二 算法设计分析过程算法设计分析过程 详细表述算法的方法详细表述算法的方法19n 归纳法、反证法等。归纳法、反证法等。二二 算法设计分析过程算法设计分析过程 证明算法的正确性证明算法的正确性201）算法设计依赖计算机的处理速度、吞吐量、）算法设计依赖计算机的处理速度、吞吐量、峰值。峰值。2）算法分析为了便于算法之间的相互比较，）算法分析为了便于算法之间的相互比较，独立于计算机处理速独立于计算机处理速 度。度。二二 算法设计分析过程算法设计分析

12、过程 算法设计与算法分析的异同点算法设计与算法分析的异同点21二二 算法设计分析过程算法设计分析过程 为算法写代码为算法写代码n程序是算法用某种程序设计语言的具体实程序是算法用某种程序设计语言的具体实现。现。22三三 为什么在计算机学科中引入算法为什么在计算机学科中引入算法 n重用性重用性尤指一种为在有限步骤内解决问题而建立尤指一种为在有限步骤内解决问题而建立的可的可重复应用重复应用的计算过程。的计算过程。 n正确、高效正确、高效n专业的计算机软件人员和发烧友的差别专业的计算机软件人员和发烧友的差别n计算机科学的核心是算法计算机科学的核心是算法23三三 为什么在计算机学科中引入算法为什么在计算机学科中引入算法 算法存