算法效率分析与分治法的应用ppt课件

1、算法效率与分治算法的运用长沙市一中曹利国算法效率的评价 n算法的评价算法的评价 n有时求解同一个问题经常有多种可用的有时求解同一个问题经常有多种可用的算法，在一定的条件下当然要选择运用算法，在一定的条件下当然要选择运用好的算法。用什么方法评价算法的好坏好的算法。用什么方法评价算法的好坏呢？通常运用算法复杂性这一概念来评呢？通常运用算法复杂性这一概念来评价算法。价算法。 算法评价 n算法执行时间需经过根据该算法编制的程序在计算机上运转时所耗费的时间来度量。而度量一个程序的执行时间通常有两种方法： n事后统计的方法 n事前分析估算的方法 算法评价 n一个用高级程序文语编写的程序在计算机上运转时所耗

2、费的时间取决于以下要素：n根据的算法选用何种战略；n问题的规模.例如求100以内还是1000以内的素数；n书写程序的言语.对于同一个算法,实现言语的级别越高,执行效率就越低；n编译程序所产生的机器代码的质量；n机器执行指令的速度。 算法评价 n一个算法是由控制构造顺序、分支和循环三种和原操作指固有数据类型的操作构成的，那么算法时间取决于两者的综合效果。 n为了便于比较同一问题的不同算法，经过的做法是，从算法中选取一种对于所研讨的问题或算法类型来说是根本运算的原操作，以该根本操作反复执行的次数作为算法的时间度量。 算法评价 n普通情况下，算法中根本操作反复执行的次数是问题规模n的某个函数fn，算

3、法的时间量度记作nTn= Ofnn它表示问题规模n的增大算法执行时间的增长率和fn的增长率一样，称作算法的渐进时间复杂度，简称时间复杂度。算法评价 n例如：在以下三个程序段中，nx:=x+1nfor i:=1 to n do x:=x+1;nfor j:=1 to n do n for k:=1 to n do x:=x+1n含根本操作“x增1的语句x:=x+1的频度分别为1，n和 n2 ，那么这三个程序段的时间复杂度分别为O1，On，On2，分别称为常量阶、线性阶和平方阶。 算法评价 n算法还能够呈现的时间复杂度有：对数阶Olog n，指数阶O2n等。在n很大时, 不同数量级时间复杂度显然有

4、O1Olog nOnOnlog nOn2 On3O2n，可以看出，在算法设计时，我们应该尽能够选用多项式阶O(nk)的算法，而不希望用指数阶的算法。 算法评价 n由于算法的时间复杂度思索的只是对于问题规模n的增长率，那么在难以计算根本操作执行次数(或语句频度)的情况下，只需求出它关于n的增长率或阶即可。n例如，在以下程序段中：nfor i:=2 to n do n for j:=2 to i-1 do x:=x+1n语句x:=x+1执行次数关于n的增长率为n2，它是语句频度表达式(n-1)(n-2)/2中增长最快的一项。 算法评价 n类似于算法的时间复杂度，以空间复杂度作为算法所需存储空间的量

5、度，记作nS(n)=O(f(n) n其中n为问题的规模(或大小)。一个上机执行的程序除了需求存储空间来存放本身所用指令、常数、变量和输入数据外，也需求一些对数据进展操作的任务单元和存储一些为实现计算所需信息的辅助空间。 算法评价 n评价一个数学模型有以下几个原那么：n1.时间复杂度n一个好的算法普通效率比较高。在竞赛中，试题经常会做一些算法运转时间上的限制。这就要求我们所建立的数学模型对应算法的效率一定要符合要求。这也是最重要的一个原那么。算法评价 n2.2.空间复杂度空间复杂度n出于计算机本身的限制，程序在出于计算机本身的限制，程序在运转时普通只被提供有限的内存空间。运转时普通只被提供有限的

6、内存空间。这也就要求我们建立模型时顾及到这一这也就要求我们建立模型时顾及到这一点。但对于模型对应的算法来说，并不点。但对于模型对应的算法来说，并不是要求空间越低越好，只需不超越内存是要求空间越低越好，只需不超越内存限制就可以了。限制就可以了。 算法评价 n3.3.编程复杂度编程复杂度n相对而言，相对而言，“编程复杂度的要编程复杂度的要求要略低一些。但是在竞赛中，假设建求要略低一些。但是在竞赛中，假设建立的算法实现起来非常繁琐，自然不利立的算法实现起来非常繁琐，自然不利于竞赛。所以，在建立模型时特别是于竞赛。所以，在建立模型时特别是在竞赛中这点也要纳入思索之中。在竞赛中这点也要纳入思索之中。 影

7、响算法效率的要素n问题的算法模型的建立n问题的数据构造选择算法评价 n一道标题能够对应几种不同思想的模型，就要根据评价模型的规范来衡量一下，确定一个模型作为分析方向。这时的评价规范除了上述的时间、空间、编程三个规范外，还要加上一个思想的复杂度。 算法评价 n所谓思想的复杂度，是指思索所耗费的时间和精神。假设我们确定了一个模型作为分析的方向没有思索思想复杂度，从问题原型到该数学模型的建模过程却非常复杂，导致思想耗费时间长，精神多，那自然是不合算的。总的来说，对于多种数学模型的选择，我们遵照“边分析，边选择的原那么。 不同数据构造对算法效率的影响乘船问题：有N个人需求乘船，而每船最多只能载两人，且

8、必需同名或同姓。求最少需求多少条船。问题分析n看到这道题，很多人都会想到图的数据构造：将N个人看作无向图的N个点，凡同名或同姓的人之间都连上边。n要满足用船最少的条件，就是需求尽量多的两人共乘一条船，表如今图中就是要用最少的边完成对一切顶点的覆盖。这就正好对应了图论的典型问题：求最小边的覆盖。所用的算法为“求恣意图最大匹配的算法。分析n运用“求恣意图最大匹配的算法比较复杂(要用到扩展交错树，对花的收缩等等)，效率也不是很高。因此，我们必需寻觅一个更简单高效的方法。n首先，由于图中任两个连通分量都是相对独立的，也就是说任一条匹配边的两顶点，都只属于同一个连通分量。因此，我们可以对每个连通分量分别

9、进展处置，而不会影响最终的结果。n同时，我们还可以对需求船只s的下限进展估计：n对于一个包含Pi个顶点的连通分量，其最小覆盖边数显然为Pi/2。假设图中共有L个连通分量，那么s=Pi/2(1=i=L)。n 然后，我们经过多次尝试，可得出一个猜测：n实践需求的覆盖边数完全等于我们求出的下限Pi/2(1=i=L)。n采用图的数据构造得出的算法为：n 每次输出一条非桥的边，并从图中将边的两顶点删去。n 此算法的时间复杂度为O(n3)。n寻觅一条非桥边的复杂度为O(n2)，寻觅覆盖边操作的复杂度为O(n)采用树构造处理n首先，我们以连通分量中任一个顶点作为树根，然后我们来确定建树的方法：n1找出与根结

10、点i同姓的点jj不在二叉树中作为i的左儿子，再以j为树根建立子树。n2找出与根结点i同名的点kk不在二叉树中作为i的右儿子，再以k为树根建立子树。证明n包含m个结点的二叉树Tm，只需求船的数量为boatm=m/2(mN)。nproc try(father:integer;var root:integer;var rest:byte);n输出root为树根的子树的乘船方案，father=0表示root是其父亲的左儿子，nfather=1表示root是其父亲的右儿子，rest表示输出子树的乘船方案后，n能否还剩下一个根结点未乘船beginvisitroot:=true; 标志root已访问找到一个

11、与root同姓且未访问的结点j; if jn+1 then try(0,j,lrest);找到一个与root同姓且未访问的结点k; if kn+1 then try(1,k,rrest);nif (lrest=1) xor (rrest=1) then begin 判别root能否只需一个儿子，情况一nif lrest=1 then print(lrest,root) else print(rrest,root);nrest:=0;nendnelse if (lrest=1) and (rrest=1) then begin 判别root能否有两个儿子if father=0 then begi

12、nprint(rrest,root);root:=j; 情况二end else beginprint(lrest,root);root:=k; 情况三End;rest:=1;endelse rest:=1;end; 这只是输出一棵二叉树的乘船方案的算法，要输出一切人的乘船方案，我们还需再加一层循环，用于寻觅各棵二叉树的根结点，但由于每个点都只会访问一次，寻觅其左右儿子各需进展一次循环，所以算法的时间复杂度为O(n2)。分治思想分治思想n假设在将规模为n的问题分成k个不同子集合的情况下，能得到k个不同的可分别求解的子问题，其中1k=n，而且在求出了这些子问题的解之后，还可找到适当的方法把它们合并

13、成整个问题的解，那么，具备上述特性的问题可思索运用分治战略设计求解。这种设计求解的思想就是将整个问题分成假设干个小问题后分而治之。 分治思想分治思想n分治(divide-and-conquer)就是“分而治之的意思，其本质就是将原问题分成n个规模较小而构造与原问题类似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。其三个步骤如下；n分解(Divide)：将原问题分成一系列子问题。n处理(Conquer)：递归地解各子问题。假设子问题足够小，那么可直接求解。n合并(combine)；将子问题的结果合并成原问题的解。 分治思想分治思想问题S问题S问题SS的解问题S1问题S2问题S

14、i问题SnS1的解S2的解Si的解Sn的解问题的分解子集解的合并子问题求解分治思想分治思想n由分治法所得到的子问题与原问题具有一样的类型。假设得到的子问题相对来说还太大，那么可反复运用分治战略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。n要使分治算法效率高，关键在于如何分割？普通地，出于一种平衡原那么，总是把大问题分成K个规模尽能够相等的子问题，但也有例外，如求表的最大最小元问题的算法，当n6时，等分定量成两个规模为3的子表L1和L2不是最正确分割。例题1：消除隐藏线n在计算机辅助设计(CAD)中，有一个经典问题：消除隐藏线被其

15、它图形遮住的线段。他需求设计一个软件，协助建筑师绘制城市的侧视轮廓图。为了方便处置，限定一切的建筑物都是矩形的，而且全部建立在同一程度面上。每个建筑物用一个三元组表示(Li,Hi,Ri)其中Li和Ri分别是建筑物i 的左右边缘坐标，Hi是建筑物i的高度。n下面左图中的建筑物分别用如下三元组表示：n(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3n,25),(19,18,22),(23,13,29),(24,4,28)n下面图中的城市侧视轮廓线用如下的序列表示：n(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)分析n

16、此题其实是矩形覆盖问题的特殊情形固定了矩形的下边境。此题可以运用矩形切割或者离散化加上线段树处理，但是前者的时间复杂度在最坏情况下能够到达O(n3)，而后者的编程实现比较复杂。n要求n个矩形的轮廓，先将这n个矩形分成两个大小相等的部分，分别求其轮廓，然后再将这两个轮廓合并。n规模为1的问题可以直接处理。详细来说，假设这个矩形的三元组表示为(L,H,R)，那么其轮廓为(L,H,R,0)。n对于规模为k的问题，假设得到了两个规模为k/2的轮廓，分别为A和B，我们如何得到合并后的轮廓C？首先，容易证明轮廓C的每一个横坐标，都来源于轮廓A和B的横坐标，而不会产生新的坐标值。因此，我们只需计算A和B中一

17、切涉及到的横坐标在C中的高度。n由于轮廓C中的横坐标值要求有序，我们可以仿照归并排序的方法，用两个指针扫描轮廓A和B。n 详细的方法是，设指针i指向轮廓A的当前横坐标，指针j指向轮廓B的当前横坐标。假设指针i指向的横坐标较小，那么将这一横坐标参与到C中，且在C中的高度为A中第i个横坐标对应的高度与B中第j-1个横坐标对应的高度的最大值。n然后将指针i向后移一位；指针j指向的横坐标较小的情况那么类似处置。假设两个指针指向的横坐标一样，此时只需将这一横坐标参与到C中一次，且高度为两指针指向高度的最大值，然后将两指针同时向后移一位。最后，需求扫描一遍轮廓C，将相邻的高度一样的横坐标合并。n分析时间复

18、杂度，T(n)=O(nlogn)。空间方面，由于递归的层数为O(logn)，每一层需求保管O(n)的空间，所以总的空间复杂度为O(nlogn)。例题2：Bone Sort(ZJU1440)n求一个未排序的序列需求经过多少次交换操作才干使序列升序有序，并且求出原序列中有多少个逆序对。n算法思想：算法思想：n按照顺序扫描序列的每一位，假设此位尚未按照顺序扫描序列的每一位，假设此位尚未调整至升序要求那么进展一次交换。调整至升序要求那么进展一次交换。详细实现：详细实现：1预处置：对原序列升序排序复杂度O(NLog2N)。2依次检查原序列的每一位复杂度O(N)： 判别该位置目前的值能否与排序后的等位的值一样 一样那么继续检查下一位 否那么将当前位置值与排序后等位的值所在的位置交换，更新交换次数求逆序对n求逆序对有多种方法， 目前运用比较广泛且实现比较简单的主要有三种算法：n1、归并排序n2、线段树n3、树状数组归并排序方法求逆序对 假设当前需求归并l, mid 和mid+1, r 两段区间，设前一段区间当前指针为p， 后一段区间指针为q。假设当前存在apaq 那么可知p, mid这段区间内一切的数都与aq构成一个逆序对，那么把ans 值加上mid-p+1 就行了。归并排序求逆序对的时间复杂度为o(n*logn)，空间复杂度也只需o(