算法设计与分析王红梅第1章绪论.ppt
- 文档编号:18939843
- 上传时间:2024-03-02
- 格式:PPT
- 页数:39
- 大小:166.54KB
算法设计与分析王红梅第1章绪论.ppt
《算法设计与分析王红梅第1章绪论.ppt》由会员分享,可在线阅读,更多相关《算法设计与分析王红梅第1章绪论.ppt(39页珍藏版)》请在冰点文库上搜索。
算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法设计与分析算法设计与分析王红梅王红梅编著编著普通高校计算机专业特色教材精选普通高校计算机专业特色教材精选2021/6/121算法设计与分析算法设计与分析清华大学出版社清华大学出版社本书主要内容本书主要内容第第1章章绪论绪论第第2章章NP完全理论完全理论第第3章章蛮力法蛮力法第第4章章分治法分治法第第5章章减治法减治法第第6章章动态规划法动态规划法2021/6/122算法设计与分析算法设计与分析清华大学出版社清华大学出版社本书主要内容(续)本书主要内容(续)第第7章章贪心法贪心法第第8章章回溯法回溯法第第9章章分支限界法分支限界法第第10章章概率算法概率算法第第11章章近似算法近似算法第第12章章计算复杂性理论计算复杂性理论2021/6/123算法设计与分析算法设计与分析清华大学出版社清华大学出版社第第1章章绪绪论论算法理论的两大论题:
算法理论的两大论题:
1.1.算法设计算法设计2.2.算法分析算法分析2021/6/124算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.1算法的基本概念算法的基本概念1.1.1为什么要学习算法为什么要学习算法1.1.2算法及其重要特性算法及其重要特性1.1.3算法的描述方法算法的描述方法1.1.4算法设计的一般过程算法设计的一般过程1.1.5重要的问题类型重要的问题类型2021/6/125算法设计与分析算法设计与分析清华大学出版社清华大学出版社问题的求解过程:
问题的求解过程:
分析问题分析问题设计算法设计算法编写程序编写程序整理结果整理结果程序设计研究的四个层次:
程序设计研究的四个层次:
算法算法方法学方法学语言语言工具工具1.1.1为什么要学习算法为什么要学习算法理由理由11:
算法:
算法程序的灵魂程序的灵魂理由理由22:
提高分析问题的能力:
提高分析问题的能力算法的形式化算法的形式化思维的逻辑性、条理性思维的逻辑性、条理性2021/6/126算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.1.2算法及其重要特性算法及其重要特性算法(算法(Algorithm):
对特定问题求解):
对特定问题求解步骤的一种描述,是指令的有限序列。
步骤的一种描述,是指令的有限序列。
2021/6/127算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法的五大特性:
算法的五大特性:
输入:
一个算法有零个或多个输入。
输入:
一个算法有零个或多个输入。
输出:
一个算法有一个或多个输出。
输出:
一个算法有一个或多个输出。
有穷性:
一个算法必须总是在执行有穷步之后有穷性:
一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。
结束,且每一步都在有穷时间内完成。
确定性:
算法中的每一条指令必须有确切的含确定性:
算法中的每一条指令必须有确切的含义,对于相同的输入只能得到相同的输出。
义,对于相同的输入只能得到相同的输出。
可行性:
算法描述的操作可以通过已经实现的可行性:
算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
基本操作执行有限次来实现。
2021/6/128算法设计与分析算法设计与分析清华大学出版社清华大学出版社mnr例:
欧几里德算法例:
欧几里德算法辗转相除法求两辗转相除法求两个自然数个自然数m和和n的最大公约数的最大公约数2021/6/129算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.1.3算法的描述方法算法的描述方法自然语言优点:
容易理解缺点:
冗长、二义性使用方法:
粗线条描述算法思想注意事项:
避免写成自然段2021/6/1210算法设计与分析算法设计与分析清华大学出版社清华大学出版社输入输入m和和n;求求m除以除以n的余数的余数r;若若r等于等于00,则,则n为最大公约数,算法结束;为最大公约数,算法结束;否则执行第否则执行第步;步;将将n的值放在的值放在m中,将中,将r的值放在的值放在n中;中;重新执行第重新执行第步。
步。
欧几里德算法欧几里德算法2021/6/1211算法设计与分析算法设计与分析清华大学出版社清华大学出版社流程图流程图优点:
流程直观优点:
流程直观缺点:
缺少严密性、灵活性缺点:
缺少严密性、灵活性使用方法:
描述简单算法使用方法:
描述简单算法注意事项:
注意抽象层次注意事项:
注意抽象层次2021/6/1212算法设计与分析算法设计与分析清华大学出版社清华大学出版社N开始输入m和nr=m%nr=0m=n;n=r输出n结束Y欧几里德算法欧几里德算法2021/6/1213算法设计与分析算法设计与分析清华大学出版社清华大学出版社程序设计语言程序设计语言优点:
能由计算机执行优点:
能由计算机执行缺点:
抽象性差,对语言要求高缺点:
抽象性差,对语言要求高使用方法:
算法需要验证使用方法:
算法需要验证注意事项:
将算法写成子函数注意事项:
将算法写成子函数2021/6/1214算法设计与分析算法设计与分析清华大学出版社清华大学出版社#includeintCommonFactor(intm,intn)intr=m%n;while(r!
=0)m=n;n=r;r=m%n;returnn;voidmain()coutCommonFactor(63,54)endl;欧几里德算法2021/6/1215算法设计与分析算法设计与分析清华大学出版社清华大学出版社伪代码伪代码算法语言算法语言伪代码(伪代码(Pseudocode):
介于自然语言和):
介于自然语言和程序设计语言之间的方法,它采用某一程序程序设计语言之间的方法,它采用某一程序设计语言的基本语法,操作指令可以结合自设计语言的基本语法,操作指令可以结合自然语言来设计。
然语言来设计。
优点:
表达能力强,抽象性强,容易理解优点:
表达能力强,抽象性强,容易理解使用方法:
使用方法:
722021/6/1216算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;欧几里德算法欧几里德算法2021/6/1217算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.1.4算法设计的一般过程算法设计的一般过程11理解问题理解问题22预测所有可能的输入预测所有可能的输入3.3.在精确解和近似解在精确解和近似解间做做选择4.4.确定适当的数据结构确定适当的数据结构55算法设计技术算法设计技术66描述算法描述算法77跟踪算法跟踪算法88分析算法的效率分析算法的效率99根据算法编写代码根据算法编写代码2021/6/1218算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.1.5重要的问题类型重要的问题类型1.查找问题查找问题2.排序问题排序问题3.图问题图问题4.组合问题组合问题5.几何问题几何问题2021/6/1219算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.2算法分析算法分析1.2.1渐进符号渐进符号1.2.2最好、最坏和平均情况最好、最坏和平均情况1.2.3非递归算法的分析非递归算法的分析1.2.4递归算法的分析递归算法的分析1.2.5算法的后验分析算法的后验分析2021/6/1220算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.2算法分析算法分析算法分析(算法分析(AlgorithmAnalysis):
对算法所需):
对算法所需要的两种计算机资源要的两种计算机资源时间和空间进行估算时间和空间进行估算时间复杂性(时间复杂性(TimeComplexity)空间复杂性(空间复杂性(SpaceComplexity)算法分析的目的:
算法分析的目的:
设计算法设计算法设计出复杂性尽可能低的算法设计出复杂性尽可能低的算法选择算法选择算法在多种算法中选择其中复杂性最低者在多种算法中选择其中复杂性最低者2021/6/1221算法设计与分析算法设计与分析清华大学出版社清华大学出版社时间复杂性分析的关键:
时间复杂性分析的关键:
问题规模:
输入量的多少;问题规模:
输入量的多少;基本语句:
执行次数与整个算法的执行时间基本语句:
执行次数与整个算法的执行时间成正比的语句成正比的语句for(i=1;i=n;i+)for(j=1;j0),则有),则有T(n)=O(nm)且且T(n)=(nm),因,因此,有此,有T(n)=(nm)。
2021/6/1226算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.2.2最好、最坏和平均情况最好、最坏和平均情况例:
例:
在一维整型数组在一维整型数组An中顺序查找与给定值中顺序查找与给定值k相等相等的元素(假设该数组中有且仅有一个元素值为的元素(假设该数组中有且仅有一个元素值为k)intFind(intA,intn)for(i=0;in;i+)if(Ai=k)break;returni;2021/6/1227算法设计与分析算法设计与分析清华大学出版社清华大学出版社最好情况:
出现概率较大时分析最好情况:
出现概率较大时分析最差情况:
实时系统最差情况:
实时系统平均情况:
已知输入数据是如何分布的,平均情况:
已知输入数据是如何分布的,通常假设等概率分布通常假设等概率分布结论:
如果问题规模相同,时间代价与输结论:
如果问题规模相同,时间代价与输入数据有关,则需要分析最好情况、最坏入数据有关,则需要分析最好情况、最坏情况、平均情况。
情况、平均情况。
2021/6/1228算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.2.3非递归算法的分析非递归算法的分析算法算法非递归算法、递归算法非递归算法、递归算法例:
求数组最小值算法例:
求数组最小值算法intArrayMin(inta,intn)min=a0;for(i=1;in;i+)if(ai+=15)2(217)(2nnnTnnT)(10310)212(57257)(22212102nOnnnnnnnnTkkii=-=-+=+=-=222112222225)2(52)2(52)1(25)2(5)4(5)8(2(2(25)2(5)4(2(25)2
(2)(nnnTnnnnTnnnTnnTnTkkk+=+=+=+=-LL2021/6/1232算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.通用分治递推式通用分治递推式大小为大小为n的原问题分成若干个大小为的原问题分成若干个大小为n/b的子问题,的子问题,其中其中a个子问题需要求解,而个子问题需要求解,而cnk是合并各个子问题是合并各个子问题的解需要的工作量。
的解需要的工作量。
+=1)
(1)(ncnbnaTncnTk=kkkbkkabanObannObanOnTb)()log()()(log2021/6/1233算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.2.5算法的后验分析算法的后验分析算法的后验分析(算法的后验分析(Posteriori)也称)也称算法的实验分析,它是一种事后计算算法的实验分析,它是一种事后计算的方法,通常需要将算法转换为对应的方法,通常需要将算法转换为对应的程序并上机运行。
的程序并上机运行。
2021/6/1234算法设计与分析算法设计与分析清华大学出版社清华大学出版社一般步骤:
一般步骤:
1.明确实验目的明确实验目的2.决决定定度度量量算算法法效效率率的的方方法法,为为实实验验准准备备算算法法的的程序实现程序实现3.决定输入样本,生成实验数据决定输入样本,生成实验数据4.对对输输入入样样本本运运行行算算法法对对应应的的程程序序,记记录录得得到到的的实验数据实验数据5.分析得到的实验数据分析得到的实验数据2021/6/1235算法设计与分析算法设计与分析清华大学出版社清华大学出版社表格法记录实验数据表格法记录实验数据129,799113,06391,27478,69267,27253,01039,99224,30311,966次数次数900080007000600050004000300020001000规模模散点图记录实验数据散点图记录实验数据执行次数或时间问题规模n2021/6/1236算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.3实验项目实验项目求最大公约数求最大公约数1.实验题目实验题目求两个自然数求两个自然数m和和n的最大公约数。
的最大公约数。
2.实验目的实验目的复习数据结构课程的相关知识,实现课程间的平滑过渡;复习数据结构课程的相关知识,实现课程间的平滑过渡;掌握并应用算法的数学分析和后验分析方法;掌握并应用算法的数学分析和后验分析方法;理理解解这这样样一一个个观观点点:
不不同同的的算算法法能能够够解解决决相相同同的的问问题题,这这些算法的解题思路不同,复杂程度不同,解题效率也不同。
些算法的解题思路不同,复杂程度不同,解题效率也不同。
2021/6/1237算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.实验要求实验要求至少设计出三个版本的求最大公约数算法;至少设计出三个版本的求最大公约数算法;对所设计的算法采用大对所设计的算法采用大O符号进行时间复杂性分析;符号进行时间复杂性分析;上上机机实实现现算算法法,并并用用计计数数法法和和计计时时法法分分别别测测算算算算法法的的运行时间;运行时间;通过分析对比,得出自己的结论。
通过分析对比,得出自己的结论。
2021/6/1238算法设计与分析算法设计与分析清华大学出版社清华大学出版社用于科普,若有不用于科普,若有不当之处,请指正,感当之处,请指正,感谢您的下载。
谢您的下载。
2021/6/1239
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 红梅 绪论