算法设计与分析教案.doc

算法设计与分析教案张静第1章 绪 论 算法理论的两大论题：1. 算法设计2. 算法分析1.1 算法的基本概念1。1。1 为什么要学习算法 理由1：算法程序的灵魂 问题的求解过程：分析问题设计算法编写程序整理结果 程序设计研究的四个层次:算法方法学语言工具理由2:提高分析问题的能力算法的形式化思维的逻辑性、条理性1.1。2 算法及其重要特性 算法(Algorithm）:对特定问题求解步骤的一种描述，是指令的有限序列.算法的五大特性： 输入：一个算法有零个或多个输入。 输出:一个算法有一个或多个输出。 有穷性：一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。 确定性：算法中的每一条指令必须有确切的含义,对于相同的输入只能得到相同的输出. 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。1.1。3 算法的描述方法 自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想 注意事项：避免写成自然段欧几里德算法N开始输入m和n r=m % nr=0m=n；n=r 输出n结束Y 程序设计语言优点:能由计算机执行 缺点:抽象性差，对语言要求高使用方法:算法需要验证注意事项：将算法写成子函数欧几里德算法#include iostream。hint 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)0）,则有T（n）=O（nm)且T（n）=（n m）,因此，有T(n）=(n m）。 1.2。2 最好、最坏和平均情况 例： 在一维整型数组An中顺序查找与给定值k相等的元素(假设该数组中有且仅有一个元素值为k） int Find（int A ， int n) for （i=0； in； i+) if （Ai= =k） break; return i; 结论：如果问题规模相同,时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。 最好情况：出现概率较大时分析 最差情况：实时系统 平均情况:已知输入数据是如何分布的， 通常假设等概率分布1。2。3 非递归算法的分析 算法-非递归算法、递归算法 例：求数组最小值算法 int ArrayMin（int a ， int n) min=a0; for (i=1； in； i+) if (aimin） min=ai； return min; 非递归算法分析的一般步骤: 1. 决定用哪个（或哪些）参数作为算法问题规模的度量2。 找出算法中的基本语句3. 检查基本语句的执行次数是否只依赖于问题规模4. 建立基本语句执行次数的求和表达式5. 用渐进符号表示这个求和表达式v 关键：建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 1.2。4 递归算法的分析 关键：根据递归过程建立递推关系式，然后求解这个递推关系式。1。 猜测技术:对递推关系式估计一个上限，然后（用数学归纳法）证明它正确。2. 扩展递归技术 3。 通用分治递推式大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题需要求解,而cnk是合并各个子问题的解需要的工作量。 1.2。5 算法的后验分析 算法的后验分析（Posteriori）也称算法的实验分析，它是一种事后计算的方法，通常需要将算法转换为对应的程序并上机运行。一般步骤：1。 明确实验目的 2。 决定度量算法效率的方法，为实验准备算法的程序实现3。 决定输入样本,生成实验数据 4. 对输入样本运行算法对应的程序，记录得到的实验数据5. 分析得到的实验数据 表格法记录实验数据 散点图记录实验数据 执行次数或时间 问题规模n第4章 分治法 4。1 概 述 4.1.1 分治法的设计思想 将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破,分而治之。更一般地说,将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题,如此分解下去，直到问题规模足够小，很容易求出其解为止,再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解. 启发式规则：1。 平衡子问题:最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想,它几乎总是比子问题规模不等的做法要好。2. 独立子问题:各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。 分治法的典型情况 子问题1的规模是n/2 子问题1的解 子问题2的解 子问题2的规模是n/2 原问题的解 原问题的规模是n4。1。2 分治法的求解过程 一般来说,分治法的求解过程由以下三个阶段组成：（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题,并尽量使这k个子问题的规模大致相同。（2)求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现.（3）合并：把各个子问题的解合并起来,合并的代价因情况不同有很大差异,分治算法的有效性很大程度上依赖于合并的实现。 分治法的一般过程DivideConquer（P)if（P的规模足够小)直接求解P;分解为k个子问题P1,P2,Pk；for(i=1；i=k;i+) yi= DivideConquer(Pi);return Merge（y1，,yk)；例：计算an，应用分治技术得到如下计算方法： 34 32 32 81 31 31 9 31 31 9 3 3 3 3分解问题求解每个子问题合并子问题的解4。2 递 归 4。2.1 递归的定义 递归就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己,是一种描述问题和解决问题的基本方法。递归有两个基本要素： 边界条件：确定递归到何时终止; 递归模式:大问题是如何分解为小问题的,确定递归体.4。2。2 递归函数的运行轨迹 在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次,如果把调用递归函数的主函数称为第0层，进入函数后,首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层.采用图示方法描述递归函数的运行轨迹,从中可较直观地了解到各调用层次及其执行情况。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)结束4。2。3 递归函数的内部执行过程 一个递归函数的调用过程类似于多个函数的嵌套调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：（1）运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；(2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈;（3)每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。汉诺塔算法在执行过程中，工作栈的变化下图所示,其中栈元素的结构为（返回地址，n值,A值，B值，C值），返回地址对应算法中语句的行号。递归算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此，它为设计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具.但是，因为递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的运行效率较低。 4。3 排序问题中的分治法4。3。1 归并排序二路归并排序的分治策略是：（1）划分：将待排序序列r1， r2, , rn划分为两个长度相等的子序列r1， , rn/2和rn/21, , rn；(2）求解子问题:分别对这两个子序列进行排序，得到两个有序子序列；（3)合并：将这两个有序子序列合并成一个有序序列。算法4.3归并排序 void MergeSort（int r ， int r1 , int s, int t) if （s= =t) r1s=rs； else m=(s+t)/2； Mergesort（r， r1， s, m）; /归并排序前半个子序列 Mergesort(r, r1， m+1， t); /归并排序后半个子序列 Merge（r1, r, s， m， t)； /合并两个已排序的子序列 算法4.4合并有序子序列 void Merge（int r ， int r1 , int s, int m， int t） i=s; j=m+1; k=s； while (i=m & j=t) if (ri=rj) r1k+=ri+; /取ri和rj中较小者放入r1k else r1k+=rj+; if （i=m） while （i=m) /若第一个子序列没处理完,则进行收尾处理 r1k+=ri+; else while （j+=1)2(211)(nnnTnnT根据1。2.4节的主定理，二路归并排序的时间代价是O(nlog2n).二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂性为O（n)。 4.3。2 快速排序 快速排序的分治策略是:(1）划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1 ri-1和ri+1 rn,前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；（2）求解子问题：分别对划分后的每一个子序列递归处理；（3)合并：由于对子序列r1 ri-1和ri+1 rn的排序是就地进行的，所以合并不需要执行任何操作。v 归并排序按照记录在序列中的位置对序列进行划分，v 快速排序按照记录的值对序列进行划分。以第一个记录作为轴值,对待排序序列进行划分的过程为：（1)初始化：取第一个记录作为基准，设置两个参数i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；（2)右侧扫描过程:将基准记录与j指向的记录进行比较，如果j指向记录的关键码大，则j前移一个记录位置。重复右侧扫描过程，直到右侧的记录小（即反序），若ij，则将基准记录与j指向的记录进行交换;（3）左侧扫描过程：将基准记录与i指向的记录进行比较,如果i指向记录的关键码小，则i后移一个记录位置。重复左侧扫描过程，直到左侧的记录大（即反序），若ij，则将基准记录与i指向的记录交换；（4）重复(2）（3)步，直到i与j指向同一位置，即基准记录最终的位置。一次划分示例1365275038495513652750384955j13652750384955i算法4.5一次划分 int Partition(int r , int first， int end） i=first; j=end; /初始化 while (ij) while (ij & ri= rj） j-; /右侧扫描 if （ij） rirj； /将较小记录交换到前面 i+; while （ij & ri= rj） i+； /左侧扫描 if (ij) rjri; /将较大记录交换到后面 j-; retutn i; / i为轴值记录的最终位置 以轴值为基准将待排序序列划分为两个子序列后，对每一个子序列分别递归进行排序.算法4.6-快速排序 void QuickSort(int r , int first, int end) if （first0) sum=aleft； else sum=0; else center=(left+right)/2； /划分 leftsum=MaxSum（a, left, center)； /对应情况，递归求解 rightsum=MaxSum(a, center+1， right); /对应情况，递归求解s1=0; lefts=0; /以下对应情况，先求解s1 for （i=center； i=left； i) lefts+=ai; if (leftss1） s1=lefts； s2=0; rights=0； /再求解s2 for (j=center+1； j=right; j+) rights+=aj; if （rightss2) s2=rights； sum=s1+s2； /计算情况的最大子段和 if （sumleftsum） sum=leftsum； /合并，在sum、leftsum和rightsum中取较大者 if (sumrightsum） sum=rightsum； return sum;分析算法4.7的时间性能,对应划分得到的情况和，需要分别递归求解，对应情况，两个并列for循环的时间复杂性是O（n),所以,存在如下递推式：根据1.2.4节主定理,算法4.7的时间复杂性为O(nlog2n)。 4.4.2 棋盘覆盖问题 在一个2k2k （k0)个方格组成的棋盘中，恰有一个方格与其他方格不同,称该方格为特殊方格。棋盘覆盖问题要求用图4。11(b）所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖.分治法求解棋盘覆盖问题的技巧在于划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。k0时，可将2k2k的棋盘划分为4个2k-12k-1的子棋盘，这样划分后,由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格,其余3个子棋盘中没有特殊方格.为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,从而将原问题转化为4个较小规模的棋盘覆盖问题.递归地使用这种划分策略,直至将棋盘分割为11的子棋盘。下面讨论棋盘覆盖问题中数据结构的设计.（1）棋盘：可以用一个二维数组boardsizesize表示一个棋盘,其中,size=2k。为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量；(2）子棋盘：整个棋盘用二维数组boardsizesize表示,其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示; (3）特殊方格:用boarddrdc表示特殊方格，dr和dc是该特殊方格在二维数组board中的下标; （4） L型骨牌:一个2k2k的棋盘中有一个特殊方格,所以，用到L型骨牌的个数为（4k1）/3，将所有L型骨牌从1开始连续编号,用一个全局变量t表示。 算法4。8棋盘覆盖void ChessBoard(int tr， int tc, int dr， int dc, int size)/ tr和tc是棋盘左上角的下标，dr和dc是特殊方格的下标，/ size是棋盘的大小,t已初始化为0 if （size = = 1) return； /棋盘只有一个方格且是特殊方格 t+; / L型骨牌号 s = size/2； / 划分棋盘 / 覆盖左上角子棋盘 if (dr = tr + s & dc tc + s) / 特殊方格在左下角子棋盘中 ChessBoard（tr+s, tc, dr， dc， s）; /递归处理子棋盘 else / 用 t 号L型骨牌覆盖右上角,再递归处理子棋盘 boardtr + stc + s - 1 = t; ChessBoard(tr+s, tc, tr+s， tc+s-1， s）； / 覆盖右下角子棋盘 if （dr = tr + s & dc = tc + s) / 特殊方格在右下角子棋盘中 ChessBoard(tr+s， tc+s， dr， dc， s); /递归处理子棋盘 else / 用 t 号L型骨牌覆盖左上角，再递归处理子棋盘 boardtr + stc + s = t； ChessBoard(tr+s, tc+s， tr+s， tc+s， s); 设T(k）是覆盖一个2k2k棋盘所需时间,从算法的划分策略可知，T（k）满足如下递推式： 解此递推式可得T（k)=O（4k）。由于覆盖一个2k2k棋盘所需的骨牌个数为（4k-1)/3，所以，算法4.8是一个在渐进意义下的最优算法。 4.4。3 循环赛日程安排问题 设有n=2k个选手要进行网球循环赛,要求设计一个满足以下要求的比赛日程表:（1）每个选手必须与其他n1个选手各赛一次；(2）每个选手一天只能赛一次。 按此要求，可将比赛日程表设计成一个 n 行n1列的二维表,其中，第 i 行第 j 列表示和第 i 个选手在第 j 天比赛的选手。 按照分治的策略,可将所有参赛的选手分为两部分，n2k个选手的比赛日程表就可以通过为n/22k-1个选手设计的比赛日程表来决定。递归地执行这种分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单:只要让这2个选手进行比赛就可以了。(b） 2k(k=2）个选手比赛 （c) 2k（k=3)个选手比赛显然，这个求解过程是自底向上的迭代过程，其中左上角和左下角分别为选手1至选手4以及选手5至选手8前3天的比赛日程，据此，将左上角部分的所有数字按其对应位置抄到右下角，将左下角的所有数字按其对应位置抄到右上角，这样，就分别安排好了选手1至选手4以及选手5至选手8在后4天的比赛日程，如图（c)所示。具有多个选手的情况可以依此类推。 这种解法是把求解2k个选手比赛日程问题划分成依次求解21、22、2k个选手的比赛日程问题，换言之，2k个选手的比赛日程是在2k1个选手的比赛日程的基础上通过迭代的方法求得的.在每次迭代中，将问题划分为4部分：（1）左上角：左上角为2k-1个选手在前半程的比赛日程；（2）左下角:左下角为另2k1个选手在前半程的比赛日程,由左上角加2k1得到，例如22个选手比赛，左下角由左上角直接加2得到，23个选手比赛,左下角由左上角直接加4得到；(3）右上角：将左下角直接抄到右上角得到另2k1个选手在后半程的比赛日程；（4）右下角：将左上角直接抄到右下角得到2k-1个选手在后半程的比赛日程； 算法设计的关键在于寻找这4部分元素之间的对应关系。算法4。9循环赛日程表 void GameTable（int k, int a ) / n=2k(k1）个选手参加比赛， /二维数组a表示日程安排,数组下标从1开始 n=2; /k=0，2个选手比赛日程可直接求得 /求解2个选手比赛日程,得到左上角元素 a11=1; a12=2； a21=2； a22=1; for (t=1; tk; t+） /迭代处理，依次处理22, , 2k个选手比赛日程 temp=n； n=n2； /填左下角元素 for （i=temp+1； i=n; i+ ) for （j=1; j=temp; j+) aij=ai-tempj+temp; /左下角元素和左上角元素的对应关系 /填右上角元素 for （i=1； i=temp； i+） for (j=temp+1; j=n； j+） aij=ai+temp(j+temp)% n; /填右下角元素 for (i=temp+1; i=n; i+) for （j=temp+1； j=n； j+） aij=ai-tempj-temp； 分析算法4.9的时间性能，迭代处理的循环体内部有3个循环语句,每个循环语句都是一个嵌套的for循环，且他们的执行次数相同，基本语句是最内层循环体的赋值语句，即填写比赛日程表中的元素。基本语句的执行次数是:所以，算法4.9的其时间复杂性为O(4k）。4。5 几何问题中的分治法4.5。1 最近对问题 设p1=(x1, y1）， p2=（x2, y2), ， pn=（xn, yn)是平面上n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。 严格地讲，最接近点对可能多于一对,简单起见，只找出其中的一对作为问题的解.用分治法解决最近对问题，很自然的想法就是将集合S分成两个子集 S1和 S2,每个子集中有n/2个点。然后在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步中，如果集合 S 中最接近的两个点都在子集 S1或 S2中，则问题很容易解决，如果这两个点分别在 S1和 S2中，问题就比较复杂了。为了使问题易于理解,先考虑一维的情形.此时，S中的点退化为x轴上的n个点x1, x2， ， xn。用x轴上的某个点m将S划分为两个集合S1和S2，并且S1和S2含有点的个数相同.递归地在S1和S2上求出最接近点对 (p1， p2） 和(q1, q2),如果集合S中的最接近点对都在子集S1或S2中,则d=min（p1, p2), （q1， q2）即为所求，如果集合S中的最接近点对分别在S1和S2中,则一定是(p3, q3），其中，p3是子集S1中的最大值，q3是子集S2中的最小值。按这种分治策略求解最近对问题的算法效率取决于划分点m的选取，一个基本的要求是要遵循平衡子问题的原则。如果选取m=(maxS+minS