算法设计和分析教学案

算法设计和分析教学案

ID:26130295

大小:2.12 MB

页数:81页

时间:2018-11-25

算法设计和分析教学案_第1页
算法设计和分析教学案_第2页
算法设计和分析教学案_第3页
算法设计和分析教学案_第4页
算法设计和分析教学案_第5页
资源描述:

《算法设计和分析教学案》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、WORD格式可编辑专业知识整理分享WORD格式可编辑《算法设计与分析》教案张静专业知识整理分享WORD格式可编辑专业知识整理分享WORD格式可编辑专业知识整理分享WORD格式可编辑第1章绪论算法理论的两大论题:1.算法设计2.算法分析1.1算法的基本概念1.1.1为什么要学习算法理由1:算法——程序的灵魂Ø问题的求解过程:分析问题→设计算法→编写程序→整理结果Ø程序设计研究的四个层次:算法→方法学→语言→工具理由2:提高分析问题的能力算法的形式化→思维的逻辑性、条理性1.1.2算法及其重要特性算法(Algorithm):对特定问题求解步骤的一种描述,是指令的有限序列。算法的五大特性:⑴输

2、入:一个算法有零个或多个输入。⑵输出:一个算法有一个或多个输出。⑶有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。⑷确定性:算法中的每一条指令必须有确切的含义,对于相同的输入只能得到相同的输出。⑸可行性:算法描述的操作可以通过已经实现的基本操作执行有限次来实现。1.1.3算法的描述方法⑴自然语言优点:容易理解专业知识整理分享WORD格式可编辑缺点:冗长、二义性使用方法:粗线条描述算法思想注意事项:避免写成自然段欧几里德算法N开始输入m和nr=m%nr=0m=n;n=r输出n结束Y⑶程序设计语言优点:能由计算机执行缺点:抽象性差,对语言要求高使用方法:算法需要验证

3、注意事项:将算法写成子函数欧几里德算法#includeintCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}专业知识整理分享WORD格式可编辑returnn;}voidmain(){cout<

4、等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;1.1.4算法设计的一般过程1.理解问题2.预测所有可能的输入3.在精确解和近似解间做选择4.确定适当的数据结构5.算法设计技术6.描述算法7.跟踪算法8.分析算法的效率9.根据算法编写代码1.2算法分析算法分析(AlgorithmAnalysis):对算法所需要的两种计算机资源——时间和空间进行估算Ø时间复杂性(TimeComplexity)Ø空间复杂性(SpaceComplexity)算法分析的目的:Ø设计算法——设计出复杂性尽可能低的算法Ø选择算法——在多种算法中选择其中复杂性最低者时间复杂性分析的关键:专业知识整理分

5、享WORD格式可编辑Ø问题规模:输入量的多少;Ø基本语句:执行次数与整个算法的执行时间成正比的语句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.大Ω符号定义1.2若存在两个正的常数c和n0,对于任意n≥n0,都有T(n)≥c×g(n),则称T(n)=Ω(g(n))n0问题规模n执行次数n0之前的情况无关紧要T(n)c×g(n

6、)专业知识整理分享WORD格式可编辑3.Θ符号定义1.3若存在三个正的常数c1、c2和n0,对于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n),则称T(n)=Θ(f(n))n0问题规模n执行次数n0之前的情况无关紧要T(n)c2×f(n)c1×f(n)例:T(n)=5n2+8n+1当n≥1时,5n2+8n+1≤5n2+8n+n=5n2+9n≤5n2+9n2≤14n2=O(n2)当n≥1时,5n2+8n+1≥5n2=Ω(n2)∴当n≥1时,14n2≥5n2+8n+1≥5n2则:5n2+8n+1=Θ(n2)定理1.1若T(n)=amnm+am-1nm-1+…+a1n+a0(am>0

7、),则有T(n)=O(nm)且T(n)=Ω(nm),因此,有T(n)=Θ(nm)。1.2.2最好、最坏和平均情况例:在一维整型数组A[n]中顺序查找与给定值k相等的元素(假设该数组中有且仅有一个元素值为k)intFind(intA[],intn){for(i=0;i

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。