算法设计与分析教（学）案

《算法设计与分析教（学）案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、。⑶有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。⑷确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。⑸可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。1.1.3算法的描述方法⑴自然语言优点：容易理解81缺点：冗长、二义性使用方法：粗线条描述算法思想注意事项：避免写成自然段欧几里德算法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;}81returnn;}voidmain(){cout<

4、方法：7±2欧几里德算法1.r=m%n;2.循环直到r等于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）Ø空间复杂性（SpaceComplexit

5、y）算法分析的目的：Ø设计算法——设计出复杂性尽可能低的算法Ø选择算法——在多种算法中选择其中复杂性最低者时间复杂性分析的关键：81Ø问题规模：输入量的多少；Ø基本语句：执行次数与整个算法的执行时间成正比的语句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

6、)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)813.Θ符号定义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＋

7、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），则有T(n)=O(nm)且T(n)=Ω(nm)，因此，有T(n)=Θ(nm)。1.2.2最好、最坏和平均情况例：在一维整型数组A[n]中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k）intFind(intA[],intn){

8、for(i=0;i