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

模型有以下几个原则： 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)。 „ proc try(father:integer;var root:integer;var rest:byte); „ {输出root为树根的子树的乘船， father=0表示root是其父亲的左儿子， „ father=1表示root是其父亲的右儿子，rest表 示输出子树的乘船方案后， „ 是否还剩下一个根结点未乘船} begin „ visit[root]:=true; {标记root已访问} „ 找到一个与root同姓且未访问的结点j; „ if j<>n+1 then try(0,j,lrest); „ 找到一个与root同姓且未访问的结点k; „ if k<>n+1 then try(1,k,rrest); „ if (lrest=1) xor (rrest=1) then begin {判断 root是否只有一个儿子，情况一} „ if lrest=1 then print(lrest,root) else print(rrest,root); „ rest:=0; „ end „ else if (lrest=1) and (rrest=1) then begin {判断root是否有两个儿子} if father=0 then begin „ print(rrest,root);root:=j; {情况二} end else begin print(lrest,root);root:=k; {情况三} „ End; „ rest:=1; „ end „ else rest:=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 „ 下面图中的城市侧视轮廓线用如下的序列表 示： „ (1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,2 9,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：Bone Sort(ZJU1440) „ 求一个未排序的序列需要经过多少次交 换操作才能使序列升序有序，并且求出 原序列中有多少个逆序对。 <算法Part1> „ 算法思想： „ 按照顺序扫描序列的每一位，如果此位尚未 调整至升序要求则进行一次交换。 具体实现： （1）预处理：对原序列升序排序[复杂度 O(NLog2N)]。 （2）依次检查原序列的每一位[复杂度O(N)]： 判断该位置目前的值是否与排序后的等位的 值相同 相同则继续检查下一位 否则将当前位置值与排序后等位的值所 在的位置交换，更新交换次数 求逆序对 „ 求逆序对有多种方法， 目前使用比较广 泛且实现比较简单的主要有三种算法： „ 1、归并排序 „ 2、线段树 „ 3、树状数组 归并排序方法求逆序对 假设当前需要归并[l, mid] 和[mid+1, r] 两段区 间，设前一段区间当前指针为p， 后一段区间指针为q 。假设当前存在a[p]>a[q] 那么可知[p, mid]这段区间 内所有的数都与a[q]构成一个逆序对，那么把ans 值 加上mid-p+1 就行了。 „ 归并排序求逆序对的时间复杂度为o(n*logn)，空间复 杂度也只有o(2n) 树状数组方法求逆序对 我们设想动态维护一个D(i)记录序列至目前为 止小于等于i的数的数量。下面给出算法： 算法思想： „ 按照顺序扫描排位序列的每一位，统计在此 之前出现的数中小于该数的数的数量，累加 后得到整个序列中非逆序对的数量。用总序 对的数量减去即可得到逆序对数量。 具体实现： （1）预处理：利用算法Part1中的排序结果计算出序列 中各数字的排位序列（既原序列的等位数值在升序序 列中的排位名次，以此减小数值范围）[复杂度O(N)] 。 （2）依次处理排位序列的每个位置的值[复杂度O(N)]： „ 计算序列此位置之前的元素中有多少个值小于它 的[复杂度O(Log2N)]。 „ 维护树状数组，将该元素加入。[复杂度 O(Log2N)] 算法效率与分治算法的应用 算法效率的评价 算法评价 算法评价 算法评价 算法评价 算法评价 算法评价 算法评价 算法评价 算法评价 算法评价 算法评价 影响算法效率的因素 算法评价 算法评价 不同数据结构对算法效率的影响 问题分析 分析 幻灯片编号 20 幻灯片编号 21 采用树结构解决 幻灯片编号 23 证明 幻灯片编号 25 幻灯片编号 26 幻灯片编号 27 幻灯片编号 28 幻灯片编号 29 分治思想 分治思想 分治思想 分治思想 例题1：消除隐藏线 幻灯片编号 35 幻灯片编号 36 分析 幻灯片编号 38 幻灯片编号 39 幻灯片编号 40 幻灯片编号 41 幻灯片编号 42 例题2：Bone Sort(ZJU1440) <算法Part1> 具体实现： 求逆序对 归并排序方法求逆序对 树状数组方法求逆序对 具体实现：