《算法设计与分析王红梅绪论.pptx》由会员分享，可在线阅读，更多相关《算法设计与分析王红梅绪论.pptx（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本书主要内容第 1 章 绪论第 2 章 NP完全理论第 3 章 蛮力法第 4 章 分治法第 5 章 减治法第 6 章 动态规划法 第1页/共38页本书主要内容（续）第 7 章 贪心法第 8 章 回溯法第 9 章 分支限界法第10章 概率算法第11章 近似算法第12章 计算复杂性理论第2页/共38页第第1章章 绪绪 论论 算法理论的两大论题：算法理论的两大论题：1.1.算法设计算法设计2.2.算法分析算法分析第3页/共38页1.1 算法的基本概念算法的基本概念1.1.1 为什么要学习算法为什么要学习算法1.1.2 算法及其重要特性算法及其重要特性1.1.3 算法的描述方法算法的描述方法1.1.4
2、 算法设计的一般过程算法设计的一般过程1.1.5 重要的问题类型重要的问题类型第4页/共38页 问题的求解过程：问题的求解过程：分析问题分析问题设计算法设计算法编写程序编写程序整理结果整理结果 程序设计研究的四个层次：程序设计研究的四个层次：算法算法方法学方法学语言语言工具工具1.1.1 为什么要学习算法为什么要学习算法 理由理由1 1：算法：算法程序的灵魂程序的灵魂理由理由2 2：提高分析问题的能力：提高分析问题的能力算法的形式化算法的形式化思维的逻辑性、条理性思维的逻辑性、条理性第5页/共38页1.1.2 算法及其重要特性算法及其重要特性 算法（算法（Algorithm）：对特定问题求解）
3、：对特定问题求解步骤的一种描述，是指令的有限序列。步骤的一种描述，是指令的有限序列。第6页/共38页算法的五大特性：输入：一个算法有零个或多个输入。输入：一个算法有零个或多个输入。输出：一个算法有一个或多个输出。输出：一个算法有一个或多个输出。有穷性：一个算法必须总是在执行有穷步之后有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。结束，且每一步都在有穷时间内完成。确定性：算法中的每一条指令必须有确切的含确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。义，对于相同的输入只能得到相同的输出。可行性：算法描述的操作可以通过已经实现的可行性：算法
4、描述的操作可以通过已经实现的基本操作执行有限次来实现。基本操作执行有限次来实现。第7页/共38页 欧几里德算法mnr例：欧几里德算法例：欧几里德算法辗转相除法求两辗转相除法求两个自然数个自然数 m 和和 n 的最大公约数的最大公约数第8页/共38页1.1.3 算法的描述方法算法的描述方法 自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想 注意事项：避免写成自然段第9页/共38页 输入输入m 和和n；求求m除以除以n的余数的余数r；若若r等于等于0 0，则，则n为最大公约数，算法结束；为最大公约数，算法结束；否则执行第否则执行第步；步；将将n的值放在的值放在m中，将中，将r的
5、值放在的值放在n中；中；重新执行第重新执行第步。步。欧几里德算法欧几里德算法第10页/共38页 流程图流程图 优点：流程直观优点：流程直观 缺点：缺少严密性、灵活性缺点：缺少严密性、灵活性使用方法：描述简单算法使用方法：描述简单算法注意事项：注意抽象层次注意事项：注意抽象层次第11页/共38页N开始输入m和n r=m%nr=0m=n；n=r 输出n结束Y欧几里德算法欧几里德算法第12页/共38页 程序设计语言程序设计语言优点：能由计算机执行优点：能由计算机执行 缺点：抽象性差，对语言要求高缺点：抽象性差，对语言要求高使用方法：算法需要验证使用方法：算法需要验证注意事项：将算法写成子函数注意事项
6、：将算法写成子函数第13页/共38页#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;欧几里德算法第14页/共38页 伪代码伪代码算法语言算法语言伪代码（伪代码（Pseudocode）：介于自然语言和）：介于自然语言和程序设计语言之间的方法，它采用某一程序程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自设计语言的基本语法，操作指令可以结合自然语言来设计。然语言来设计。优点：表达
7、能力强，抽象性强，容易理解优点：表达能力强，抽象性强，容易理解使用方法：使用方法：7 2第15页/共38页 1.r=m%n;2.循环直到 r 等于0 2.1 m=n;2.2 n=r;2.3 r=m%n;3.输出 n;欧几里德算法欧几里德算法第16页/共38页1.1.4 算法设计的一般过程算法设计的一般过程 1 1理解问题理解问题2 2预测所有可能的输入预测所有可能的输入3.3.在精确解和近似解间做选择在精确解和近似解间做选择 4.4.确定适当的数据结构确定适当的数据结构 5 5算法设计技术算法设计技术6 6描述算法描述算法 7 7跟踪算法跟踪算法 8 8分析算法的效率分析算法的效率 9 9根据
8、算法编写代码根据算法编写代码 第17页/共38页1.1.5 重要的问题类型重要的问题类型 1.查找问题查找问题2.排序问题排序问题3.图问题图问题 4.组合问题组合问题 5.几何问题几何问题第18页/共38页1.2 算法分析算法分析1.2.1 渐进符号渐进符号1.2.2 最好、最坏和平均情况最好、最坏和平均情况1.2.3 非递归算法的分析非递归算法的分析1.2.4 递归算法的分析递归算法的分析1.2.5 算法的后验分析算法的后验分析第19页/共38页1.2 算法分析算法分析 算法分析（算法分析（Algorithm Analysis）：对算法所需）：对算法所需要的两种计算机资源要的两种计算机资源
9、时间和空间进行估算时间和空间进行估算 时间复杂性（时间复杂性（Time Complexity）空间复杂性（空间复杂性（Space Complexity）算法分析的目的：算法分析的目的：设计算法设计算法设计出复杂性尽可能低的算法设计出复杂性尽可能低的算法 选择算法选择算法在多种算法中选择其中复杂性最低者在多种算法中选择其中复杂性最低者第20页/共38页时间复杂性分析的关键：问题规模：输入量的多少；基本语句：执行次数与整个算法的执行时间 成正比的语句for(i=1;i=n;i+)for(j=1;j0），则有），则有T(n)=O(nm)且且T(n)=(n m)，因，因此，有此，有T(n)=(n m)
10、。第25页/共38页1.2.2 最好、最坏和平均情况最好、最坏和平均情况 例：例：在一维整型数组在一维整型数组A n 中顺序查找与给定值中顺序查找与给定值k相等相等的元素（假设该数组中有且仅有一个元素值为的元素（假设该数组中有且仅有一个元素值为k）int Find(int A,int n)for(i=0;in;i+)if(Ai=k)break;return i;第26页/共38页最好情况：出现概率较大时分析最好情况：出现概率较大时分析最差情况：实时系统最差情况：实时系统平均情况：已知输入数据是如何分布的，平均情况：已知输入数据是如何分布的，通常假设等概率分布通常假设等概率分布结论：如果问题规模
11、相同，时间代价与输结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏入数据有关，则需要分析最好情况、最坏情况、平均情况。情况、平均情况。第27页/共38页1.2.3 非递归算法的分析非递归算法的分析 算法算法非递归算法、递归算法非递归算法、递归算法 例：求数组最小值算法例：求数组最小值算法 int ArrayMin(int a,int n)min=a0;for(i=1;in;i+)if(ai+=15)2(217)(2nnnTnnT)(10310)212(57257)(22212102nOnnnnnnnnTkkii=-=-+=+=-=222112222225)2(52)2(
12、52)1(25)2(5)4(5)8(2(2(25)2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+=+=+=+=-LL第31页/共38页3.通用分治递推式通用分治递推式大小为大小为n的原问题分成若干个大小为的原问题分成若干个大小为n/b的子问题，的子问题，其中其中a个子问题需要求解，而个子问题需要求解，而cnk是合并各个子问题是合并各个子问题的解需要的工作量。的解需要的工作量。+=1)(1)(ncnbnaTncnTk =kkkbkkabanObannObanOnTb)()log()()(log第32页/共38页1.2.5 算法的后验分析算法的后验分析 算法的后验分析
13、（算法的后验分析（Posteriori）也称）也称算法的实验分析，它是一种事后计算算法的实验分析，它是一种事后计算的方法，通常需要将算法转换为对应的方法，通常需要将算法转换为对应的程序并上机运行。的程序并上机运行。第33页/共38页一般步骤：一般步骤：1.明确实验目的明确实验目的 2.决决定定度度量量算算法法效效率率的的方方法法，为为实实验验准准备备算算法法的的程序实现程序实现3.决定输入样本，生成实验数据决定输入样本，生成实验数据 4.对对输输入入样样本本运运行行算算法法对对应应的的程程序序，记记录录得得到到的的实验数据实验数据5.分析得到的实验数据分析得到的实验数据 第34页/共38页表格
14、法记录实验数据表格法记录实验数据 129,799113,06391,27478,69267,27253,01039,99224,30311,966次数次数900080007000600050004000300020001000规模规模散点图记录实验数据散点图记录实验数据 执行次数或时间 问题规模n第35页/共38页1.3 实验项目实验项目求最大公约数求最大公约数 1.实验题目实验题目求两个自然数求两个自然数m和和n的最大公约数。的最大公约数。2.实验目的实验目的 复习数据结构课程的相关知识，实现课程间的平滑过渡；复习数据结构课程的相关知识，实现课程间的平滑过渡；掌握并应用算法的数学分析和后验分
15、析方法；掌握并应用算法的数学分析和后验分析方法；理理解解这这样样一一个个观观点点：不不同同的的算算法法能能够够解解决决相相同同的的问问题题，这这些算法的解题思路不同，复杂程度不同，解题效率也不同。些算法的解题思路不同，复杂程度不同，解题效率也不同。第36页/共38页3.实验要求实验要求 至少设计出三个版本的求最大公约数算法；至少设计出三个版本的求最大公约数算法；对所设计的算法采用大对所设计的算法采用大O符号进行时间复杂性分析；符号进行时间复杂性分析；上上机机实实现现算算法法，并并用用计计数数法法和和计计时时法法分分别别测测算算算算法法的的运行时间；运行时间；通过分析对比，得出自己的结论。通过分析对比，得出自己的结论。第37页/共38页感谢您的观看！第38页/共38页