算法设计与分析王红梅第1章绪论.ppt
算法设计与分析,王红梅 编著,普通高校计算机专业特色教材精选,本书主要内容,第 1 章 绪论 第 2 章 NP完全理论 第 3 章 蛮力法 第 4 章 分治法 第 5 章 减治法 第 6 章 动态规划法,本书主要内容（续）,第 7 章 贪心法 第 8 章 回溯法 第 9 章 分支限界法 第10章 概率算法 第11章 近似算法 第12章 计算复杂性理论,第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中； 重新执行第步。,欧几里德算法, 流程图 优点：流程直观 缺点：缺少严密性、灵活性 使用方法：描述简单算法 注意事项：注意抽象层次,欧几里德算法, 程序设计语言 优点：能由计算机执行 缺点：抽象性差，对语言要求高 使用方法：算法需要验证 注意事项：将算法写成子函数,#include 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）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。 优点：表达能力强，抽象性强，容易理解 使用方法：7 ± 2,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，对于任意nn0，都有T(n)c×f(n)，则称T(n)=O(f(n),2. 大符号,定义1.2 若存在两个正的常数c和n0，对于任意nn0，都有T(n)c×g(n)，则称T(n)=(g(n),1.2.1 渐进符号（续）,3. 符号,定义1.3 若存在三个正的常数c1、c2和n0，对于任意nn0都有c1×f(n)T(n)c2×f(n)，则称T(n)=(f(n),1.2.1 渐进符号（续）,例： T(n)5n28n1 当n1时，5n28n15n28nn 5n29n5n29n214n2O(n2) 当n1时，5n28n15n2(n2) 当n1时，14n25n28n15n2 则：5n28n1(n2),定理1.1 若T(n)=amnm +am-1nm-1 + +a1n+a0（am0），则有T(n)=O(nm)且T(n)=(n m)，因此，有T(n)=(n m)。,1.2.2 最好、最坏和平均情况,例： 在一维整型数组An中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k）,int Find(int A , int n) for (i=0; in; i+) if (Ai= =k) break; return i; ,最好情况：出现概率较大时分析 最差情况：实时系统 平均情况：已知输入数据是如何分布的， 通常假设等概率分布,结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。,1.2.3 非递归算法的分析,算法非递归算法、递归算法,例：求数组最小值算法 int ArrayMin(int a , int n) min=a0; for (i=1; in; i+) if (aimin) min=ai; return min; ,非递归算法分析的一般步骤：,1. 决定用哪个（或哪些）参数作为算法问题规模的度量 2. 找出算法中的基本语句 3. 检查基本语句的执行次数是否只依赖于问题规模 4. 建立基本语句执行次数的求和表达式 5. 用渐进符号表示这个求和表达式 关键：建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。,1.2.4 递归算法的分析,1. 猜测技术:对递推关系式估计一个上限，然后（用数学归纳法）证明它正确。,关键：根据递归过程建立递推关系式，然后求解这个递推关系式。,2. 扩展递归技术,3. 通用分治递推式,大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题需要求解，而cnk是合并各个子问题的解需要的工作量。,1.2.5 算法的后验分析,算法的后验分析（Posteriori）也称算法的实验分析，它是一种事后计算的方法，通常需要将算法转换为对应的程序并上机运行。,一般步骤： 1. 明确实验目的 2. 决定度量算法效率的方法，为实验准备算法的程序实现 3. 决定输入样本，生成实验数据 4. 对输入样本运行算法对应的程序，记录得到的实验数据 5. 分析得到的实验数据,表格法记录实验数据,129,799,113,063,91,274,78,692,67,272,53,010,39,992,24,303,11,966,次数,散点图记录实验数据,1.3 实验项目求最大公约数,1. 实验题目 求两个自然数m和n的最大公约数。,2. 实验目的 复习数据结构课程的相关知识，实现课程间的平滑过渡； 掌握并应用算法的数学分析和后验分析方法； 理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。,3. 实验要求 至少设计出三个版本的求最大公约数算法； 对所设计的算法采用大O符号进行时间复杂性分析； 上机实现算法，并用计数法和计时法分别测算算法的运行时间； 通过分析对比，得出自己的结论。,
