算法设计与分析王红梅第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 算法分析,算法分析（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)cf(n)，则称T(n)=O(f(n),2.大符号,定义1.2 若存在两个正的常数c和n0，对于任意nn0，都有T(n)cg(n)，则称T(n)=(g(n),1.2.1 渐进符号（续）,3.符号,定义1.3 若存在三个正的常数c1、c2和n0，对于任意nn0都有c1f(n)T(n)c2f(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符号进行时间复杂性分析；上机实现算法，并用计数法和计时法分别测算算法的运行时间；通过分析对比，得出自己的结论。,
