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

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