算法设计与分析第一章绪论.ppt

算法的五大特性： 欧几里德算法 时间复杂性分析的关键： 问题规模：输入量的多少； 基本语句：执行次数与整个算法的执行时间 成正比的语句 * 第1章 绪 论 算法理论的两大论题： 1. 算法设计 2. 算法分析 1.1 算法的基本概念 1.1.1 为什么要学习算法 1.1.2 算法及其重要特性 1.1.3 算法的描述方法 1.1.4 算法设计的一般过程 1.1.5 重要的问题类型 问题的求解过程： 分析问题→设计算法→编写程序→整理结果 程序设计研究的四个层次： 算法→方法学→语言→工具 1.1.1 为什么要学习算法 理由1：算法——程序的灵魂 理由2：提高分析问题的能力 算法的形式化→思维的逻辑性、条理性 1.1.2 算法及其重要特性 算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。 ⑴ 输入：一个算法有零个或多个输入。 ⑵ 输出：一个算法有一个或多个输出。 ⑶ 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ⑷ 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 ⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 m n r 例：欧几里德算法——辗转相除法求两个自然数 m 和 n 的最大公约数 1.1.3 算法的描述方法 ⑴ 自然语言 优点：容易理解 缺点：冗长、二义性 使用方法：粗线条描述算法思想 注意事项：避免写成自然段 ① 输入m 和n； ② 求m除以n的余数r； ③ 若r等于0，则n为最大公约数，算法结束； 否则执行第④步； ④ 将n的值放在m中，将r的值放在n中； ⑤ 重新执行第②步。 欧几里德算法 ⑵ 流程图 优点：流程直观 缺点：缺少严密性、灵活性 使用方法：描述简单算法 注意事项：注意抽象层次 N 开始 输入m和n r=m % n r=0 m=n；n=r 输出n 结束 Y 欧几里德算法 ⑶ 程序设计语言 优点：能由计算机执行 缺点：抽象性差，对语言要求高 使用方法：算法需要验证 注意事项：将算法写成子函数 #include iostream.h int CommonFactor(int m, int n) { int r=m % n; while (r!=0) { m=n; n=r; r=m % n; } return n; } void main( ) { coutCommonFactor(63, 54)endl; } 欧几里德算法 ⑷ 伪代码——算法语言 伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。 优点：表达能力强，抽象性强，容易理解。 1. r = m % n; 2. 循环直到 r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出 n ; 欧几里德算法 1.1.4 算法设计的一般过程 1．理解问题 2．预测所有可能的输入 3. 在精确解和近似解间做选择 4. 确定适当的数据结构 5．算法设计技术 6．描述算法 7．跟踪算法 8．分析算法的效率 9．根据算法编写代码 1.1.5 重要的问题类型 1. 查找问题 2. 排序问题 3. 图问题 4. 组合问题 5. 几何问题 1.2 算法分析 1.2.1 渐进符号 1.2.2 最好、最坏和平均情况 1.2.3 非递归算法的分析 1.2.4 递归算法的分析 1.2.5 算法的后验分析 1.2 算法分析 算法分析（Algorithm Analysis）：对算法所需要的两种计算机资源——时间和空间进行估算 时间复杂性（Time Complexity） 空间复杂性（Space Complexity） 算法分析的目的： 设计算法——设计出复杂性尽可能低的算法 选择算法——在多种算法中选择其中复杂性最低者 for (i=1; i=n; i++) for (j=1; j=n; j++) x++; 问题规模：n 基本语句：x++ 1.2.1 渐进符号 1. 大O符号 定义1.1 若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n)) n0 问题规模n 执行次数 n0之前的情况无关紧要 T(n) c×f(n) 2. 大Ω符