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

算法效率与分治算法的应用长沙市一中曹利国算法效率的评价n算法的评估算法的评估n有时求解同一个问题常常有多种可用的算法，在一定的条件下当然要选择使用好的算法。用什么方法评估算法的好坏呢？通常使用算法复杂性这一概念来评估算法。算法评价n算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法：n事后统计的方法n事前分析估算的方法算法评价n一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：依据的算法选用何种策略；问题的规模.例如求100以内还是1000以内的素数；书写程序的语言.对于同一个算法,实现语言的级别越高,执行效率就越低；编译程序所产生的机器代码的质量；机器执行指令的速度。算法评价n一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。n为了便于比较同一问题的不同算法，通过的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作，以该基本操作重复执行的次数作为算法的时间度量。算法评价n一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间量度记作T（n）=O（f（n）n它表示问题规模n的增大算法执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。算法评价n例如：在下列三个程序段中，x:=x+1 for i:=1 to n do x:=x+1;for j:=1 to n do for k:=1 to n do x:=x+1n含基本操作“x增1”的语句x:=x+1的频度分别为1，n和 n2，则这三个程序段的时间复杂度分别为O（1），O（n），O（n2），分别称为常量阶、线性阶和平方阶。算法评价n算法还可能呈现的时间复杂度有：对数阶O（log n），指数阶O（2n）等。在n很大时,不同数量级时间复杂度显然有O（1）O（log n）O（n）O（nlog n）O（n2）O（n3）O（2n），可以看出，在算法设计时，我们应该尽可能选用多项式阶O(nk)的算法，而不希望用指数阶的算法。算法评价n由于算法的时间复杂度考虑的只是对于问题规模n的增长率，则在难以计算基本操作执行次数(或语句频度)的情况下，只需求出它关于n的增长率或阶即可。例如，在下列程序段中：for i:=2 to n do for j:=2 to i-1 do x:=x+1n语句x:=x+1执行次数关于n的增长率为n2，它是语句频度表达式(n-1)(n-2)/2中增长最快的一项。算法评价n类似于算法的时间复杂度，以空间复杂度作为算法所需存储空间的量度，记作S(n)=O(f(n)n其中n为问题的规模(或大小)。一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。算法评价n评价一个数学模型有以下几个原则：1.1.时间复杂度时间复杂度一个好的算法一般效率比较高。在竞赛中，试题常常会做一些算法运行时间上的限制。这就要求我们所建立的数学模型对应算法的效率一定要符合要求。这也是最重要的一个原则。算法评价n2.2.空间复杂度空间复杂度出于计算机自身的限制，程序在运行时一般只被提供有限的内存空间。这也就要求我们建立模型时顾及到这一点。但对于模型对应的算法来说，并不是要求空间越低越好，只要不超过内存限制就可以了。算法评价n3.3.编程复杂度编程复杂度相对而言，“编程复杂度”的要求要略低一些。但是在竞赛中，如果建立的算法实现起来十分繁琐，自然不利于比赛。所以，在建立模型时（特别是在竞赛中）这点也要纳入考虑之中。影响算法效率的因素n问题的算法模型的建立n问题的数据结构选择算法评价n一道题目可能对应几种不同思想的模型，就要根据评价模型的标准来衡量一下，确定一个模型作为分析方向。这时的评价标准除了上述的时间、空间、编程三个标准外，还要加上一个思维的复杂度。算法评价n所谓思维的复杂度，是指思考所耗费的时间和精力。如果我们确定了一个模型作为分析的方向（没有考虑思维复杂度），从问题原型到该数学模型的建模过程却十分复杂，导致思维耗费时间长，精力多，那自然是不合算的。总的来说，对于多种数学模型的选择，我们遵循“边分析，边选择”的原则。不同数据结构对算法效率的影响乘船问题：n有N个人需要乘船，而每船最多只能载两人，且必须同名或同姓。求最少需要多少条船。问题分析n看到这道题，很多人都会想到图的数据结构：将N个人看作无向图的N个点，凡同名或同姓的人之间都连上边。n要满足用船最少的条件，就是需要尽量多的两人共乘一条船，表现在图中就是要用最少的边完成对所有顶点的覆盖。这就正好对应了图论的典型问题：求最小边的覆盖。所用的算法为“求任意图最大匹配”的算法。分析n使用“求任意图最大匹配”的算法比较复杂(要用到扩展交错树，对花的收缩等等)，效率也不是很高。因此，我们必须寻找一个更简单高效的方法。n首先，由于图中任两个连通分量都是相对独立的，也就是说任一条匹配边的两顶点，都只属于同一个连通分量。因此，我们可以对每个连通分量分别进行处理，而不会影响最终的结果。n同时，我们还可以对需要船只s的下限进行估计：n对于一个包含Pi个顶点的连通分量，其最小覆盖边数显然为Pi/2。若图中共有L个连通分量，则s=Pi/2(1=i=L)。n 然后，我们通过多次尝试，可得出一个猜想：n实际需要的覆盖边数完全等于我们求出的实际需要的覆盖边数完全等于我们求出的下限下限Pi/2(1=i=L)。n采用图的数据结构得出的算法为：每次输出一条非桥的边，并从图中将边的两顶点删去。此算法的时间复杂度为O(n3)。（寻找一条非桥边的复杂度为O(n2)，寻找覆盖边操作的复杂度为O(n)）采用树结构解决n首先，我们以连通分量中任一个顶点作为树根，然后我们来确定建树的方法：n（1）找出与根结点i同姓的点j（j不在二叉树中）作为i的左儿子，再以j为树根建立子树。n（2）找出与根结点i同名的点k（k不在二叉树中）作为i的右儿子，再以k为树根建立子树。证明n包含m个结点的二叉树Tm，只需要船的数量为boatm=m/2(mN)。nproctry(father:integer;varroot:integer;varrest:byte);n输出root为树根的子树的乘船方案，father=0表示root是其父亲的左儿子，nfather=1表示root是其父亲的右儿子，rest表示输出子树的乘船方案后，n是否还剩下一个根结点未乘船beginnvisitroot:=true;标记root已访问n找到一个与root同姓且未访问的结点j;nifjn+1thentry(0,j,lrest);n找到一个与root同姓且未访问的结点k;nifkn+1thentry(1,k,rrest);nif(lrest=1)xor(rrest=1)thenbegin判断root是否只有一个儿子，情况一niflrest=1thenprint(lrest,root)elseprint(rrest,root);nrest:=0;nendnelseif(lrest=1)and(rrest=1)thenbegin判断root是否有两个儿子iffather=0thenbeginnprint(rrest,root);root:=j;情况二endelsebeginprint(lrest,root);root:=k;情况三nEnd;nrest:=1;nendnelserest:=1;nend;n这只是输出一棵二叉树的乘船方案的算法，要输出所有人的乘船方案，我们还需再加一层循环，用于寻找各棵二叉树的根结点，但由于每个点都只会访问一次，寻找其左右儿子各需进行一次循环，所以算法的时间复杂度为O(n2)。分治思想分治思想n如果在将规模为n的问题分成k个不同子集合的情况下，能得到k个不同的可分别求解的子问题，其中1k=n，而且在求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解，那么，具备上述特性的问题可考虑使用分治策略设计求解。这种设计求解的思想就是将整个问题分成若干个小问题后分而治之。分治思想分治思想n分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。其三个步骤如下；1.分解(Divide)：将原问题分成一系列子问题。2.解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解。3.合并(combine)；将子问题的结果合并成原问题的解。分治思想分治思想问题S问题S问题SS的解问题S1问题S2问题Si问题SnS1的解S2的解Si的解Sn的解问题的分解子集解的合并子问题求解分治思想分治思想n由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。n要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成K个规模尽可能相等的子问题，但也有例外，如求表的最大最小元问题的算法，当n6时，等分定量成两个规模为3的子表L1和L2不是最佳分割。例题1：消除隐藏线n在计算机辅助设计(CAD)中，有一个经典问题：消除隐藏线（被其它图形遮住的线段）。你需要设计一个软件，帮助建筑师绘制城市的侧视轮廓图。为了方便处理，限定所有的建筑物都是矩形的，而且全部建立在同一水平面上。每个建筑物用一个三元组表示(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本题其实是矩形覆盖问题的特殊情形固定了矩形的下边界。本题可以使用矩形切割或者离散化加上线段树解决，但是前者的时间复杂度在最坏情况下可能达到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中所有涉及到的横坐标在C中的高度。n由于轮廓C中的横坐标值要求有序，我们可以仿照归并排序的方法，用两个指针扫描轮廓A和B。n具体的方法是，设指针i指向轮廓A的当前横坐标，指针j指向轮廓B的当前横坐标。如果指针i指向的横坐标较小，那么将这一横坐标加入到C中，且在C中的高度为A中第i个横坐标对应的高度与B中第j-1个横坐标对应的高度的最大值。n然后将指针i向后移一位；指针j指向的横坐标较小的情况则类似处理。如果两个指针指向的横坐标相同，此时只需将这一横坐标加入到C中一次，且高度为两指针指向高度的最大值，然后将两指针同时向后移一位。最后，需要扫描一遍轮廓C，将相邻的高度相同的横坐标合并。n分析时间复杂度，T(n)=O(nlogn)。空间方面，由于递归的层数为O(logn)，每一层需要保存O(n)的空间，所以总的空间复杂度为O(nlogn)。例题2：BoneSort(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就行了。n归并排序求逆序对的时间复杂度为o(n*logn)，空间复杂度也只有o(2n)树状数组方法求逆序对我们设想动态维护一个D(i)记录序列至目前为止小于等于i的数的数量。下面给出算法：算法思想：算法思想：n按照顺序扫描排位序列的每一位，统计在此之前出现的数中小于该数的数的数量，累加后得到整个序列中非逆序对的数量。用总序对的数量减去即可得到逆序对数量。具体实现：具体实现：（1）预处理：利用算法Part1中的排序结果计算出序列中各数字的排位序列（既原序列的等位数值在升序序列中的排位名次，以此减小数值范围）复杂度O(N)。（2）依次处理排位序列的每个位置的值复杂度O(N)：n计算序列此位置之前的元素中有多少个值小于它的复杂度O(Log2N)。n维护树状数组，将该元素加入。复杂度O(Log2N)