算法设计与分析教案

《算法设计与分析》教案张静1第1章绪论算法理论的两大论题：1.算法设计2.算法分析1.1算法的基本概念1.1.1为什么要学习算法理由1：算法——程序的灵魂问题的求解过程：分析问题→设计算法→编写程序→整理结果程序设计研究的四个层次：算法→方法学→语言→工具理由2：提高分析问题的能力算法的形式化→思维的逻辑性、条理性1.1.2算法及其重要特性算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。算法的五大特性：⑴输入：一个算法有零个或多个输入。⑵输出：一个算法有一个或多个输出。⑶有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。⑷确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。⑸可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。1.1.3算法的描述方法⑴自然语言优点：容易理解2缺点：冗长、二义性使用方法：粗线条描述算法思想注意事项：避免写成自然段欧几里德算法⑶程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数欧几里德算法#includeiostream.hintCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}N开始输入m和nr=m%nr=0m=n；n=r输出n结束Y3returnn;}voidmain(){coutCommonFactor(63,54)endl;}⑷伪代码——算法语言伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解使用方法：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）空间复杂性（SpaceComplexity）算法分析的目的：设计算法——设计出复杂性尽可能低的算法选择算法——在多种算法中选择其中复杂性最低者时间复杂性分析的关键：4问题规模：输入量的多少；基本语句：执行次数与整个算法的执行时间成正比的语句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))2.大Ω符号定义1.2若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≥c×g(n)，则称T(n)=Ω(g(n))n0问题规模n执行次数n0之前的情况无关紧要T(n)c×f(n)n0问题规模n执行次数n0之前的情况无关紧要T(n)c×g(n)53.Θ符号定义1.3若存在三个正的常数c1、c2和n0，对于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，则称T(n)=Θ(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（am0），则有T(n)=O(nm)且T(n)=Ω(nm)，因此，有T(n)=Θ(nm)。1.2.2最好、最坏和平均情况例：在一维整型数组A[n]中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k）intFind(intA[],intn){for(i=0;in;i++)if(A[i]==k)break;returni;}结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。最好情况：出现概率较大时分析最差情况：实时系统平均情况：已知输入数据是如何分布的，通常假设等概率分布n0问题规模n执行次数n0之前的情况无关紧要T(n)c2×f(n)c1×f(n)61.2.3非递归算法的分析算法——非递归算法、递归算法例：求数组最小值算法intArrayMin(inta[],intn){min=a[0];for(i=1;in;i++)if(a[i]min)min=a[i];returnmin;}非递归算法分析的一般步骤：1.决定用哪个（或哪些）参数作为算法问题规模的度量2.找出算法中的基本语句3.检查基本语句的执行次数是否只依赖于问题规模4.建立基本语句执行次数的求和表达式5.用渐进符号表示这个求和表达式关键：建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。1.2.4递归算法的分析关键：根据递归过程建立递推关系式，然后求解这个递推关系式。1.猜测技术:对递推关系式估计一个上限，然后（用数学归纳法）证明它正确。2.扩展递归技术3.通用分治递推式大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题需要求解，而cnk是合并各个子问题的解需要的工作量。15)2(217)(2nnnTnnT15)2(217)(2nnnTnnT222112222225)2(52)2(52)1(25))2(5))4(5)8(2(2(25))2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk×´222112222225)2(52)2(52)1(25))2(5))4(5)8(2(2(25))2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk×´)(10310)212(57257)(22212102nOnnnnnnnnTkkii)(10310)212(57257)(22212102nOnnnnnnnnTkkii1)(1)(ncnbnaTncnTk1)(1)(ncnbnaTncnTk71.2.5算法的后验分析算法的后验分析（Posteriori）也称算法的实验分析，它是一种事后计算的方法，通常需要将算法转换为对应的程序并上机运行。一般步骤：1.明确实验目的2.决定度量算法效率的方法，为实验准备算法的程序实现3.决定输入样本，生成实验数据4.对输入样本运行算法对应的程序，记录得到的实验数据5.分析得到的实验数据表格法记录实验数据散点图记录实验数据执行次数或时间问题规模nkkkbkkabanObannObanOnTb)()log()()(logkkkbkkabanObannObanOnTb)()log()()(log129,799113,06391,27478,69267,27253,01039,99224,30311,966次数900080007000600050004000300020001000规模900080007000600050004000300020001000规模8第4章分治法4.1概述4.1.1分治法的设计思想将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。启发式规则：1.平衡子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k＝2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。2.独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。分治法的典型情况4.1.2分治法的求解过程一般来说，分治法的求解过程由以下三个阶段组成：（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，子问题1的规模是n/2子问题1的解子问题2的解子问题2的规模是n/2原问题的解原问题的规模是n9并尽量使这k个子问题的规模大致相同。（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。分治法的一般过程DivideConquer(P){if(P的规模足够小）直接求解P;分解为k个子问题P1,P2,…Pk;for(i=1;i=k;i++)yi=DivideConquer(Pi);returnMerge(y1,…,yk);}例：计算an，应用分治技术得到如下计算方法：4.2递归4.2.1递归的定义递归就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。递归有两个基本要素：3432328131319313193333分解问题求解每个子问题合并子问题的解´1122naanaannn如果如果´1122naanaannn如果如果10⑴边界条件：确定递归到何时终止；⑵递归模式：大问题是如何分解为小问题的，确定递归体。4.2.2递归函数的运行轨迹在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。采用图示方法描述递归函数的运行轨迹，从中可较直观地了解到各调用层次及其执行情况。4.2.3递归函数的内部执行过程一个递归函数的调用过程类似于多个函数的嵌套调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：（1）运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；（3）每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move(A,C)Move(A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move(C,B)Hanio(1,C,A,B)Move(A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move(B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move(A,C)Hanio(2,B,A,C)Move(B,A)Hanio(1,A,B,C)结束11汉诺塔算法在执行过程中，工作栈的变化下图所示，其中栈元素的结构为（返回地址，n值，A值，B值，C值），返回地址对应算法中语句的行号。递归算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此，它为设计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具。但是，因为递归算法是一种