算法合集之《一类算法复合的方法》

《算法合集之《一类算法复合的方法》》由会员分享，可在线阅读，更多相关《算法合集之《一类算法复合的方法》（11页珍藏版）》请在金锄头文库上搜索。

1、第 1 页，共 11 页 一类算法复合的方法 一类算法复合的方法 江苏省扬州中学 张煜承 摘要 摘要 本文讲了一类算法复合的方法。这种方法是指将一个问题的若干种算法，分别使用于这个问题中若干个互补的部分。 本文对两个有意思的问题作了详细的分析，使用了这种算法复合的方法成功解决了这两个问题。问题一中我们将一个O( )和一个O( )的算法复合，分别使用于问题中的两部分询问，得到了一个O( . )的算法。问题二中，我们将两个O( )的算法使用于原问题分割得到的三部分，得到了一个O( . )的算法。 本文最后对这类方法进行了总结。每个算法都可能有各自的优势和劣势。而将它们复合，使用于问题中的不同的部分

2、，就有可能会将它们的优势结合起来，取长补短，得出一个总体更优的算法。这种思想是极为重要的。 关键字 关键字 算法复合 方法 一、问题一一、问题一1 1 1.1 问题描述问题描述 维护一个集合 S，初始时为空。对这个集合有两种操作： 1、 B X 在集合 S 中插入一个整数 X，保证当前集合中 X 还不存在 2、 A Y 询问集合 S 中，被 Y 除余数最小的数是多少。如果有多个数余数相1 题目来源：The 2006 ACM Asia Programming Contest - Shanghai 第 2 页，共 11 页 等，取任意一个 有 N 个操作需要依次处理。计算所有询问的答案。允许离线算

3、法。 其中1 40000，1 , 500000 1.2 初步分析初步分析 这道题让我们设计算法维护一个集合 。我们先考虑一些容易想到的算法。 最容易想到的算法是直接模拟问题中规定的操作，我们称其为算法1.0。每当遇到一个询问操作 “A ” 时， 我们枚举当前集合 中的每个数， 从中找出被 除余数最小的。算法的时间复杂度为O 插入操作个数 询问操作个数 ，最坏情况下显然会超时。但当插入操作很少或询问操作很少时，这个算法会很快。 另一个略优一些的算法也很容易想到（算法1.1） 。设 ( )表示当前集合 S 中使得 x mod y 最小的数 x，也就是询问“A y”的答案。因为允许离线算法，我们可以

4、事先整理出询问中所有不同的 Y 组成的集合 T，然后我们对每个 维护( )的值。每当插入一个数的时候，我们用O(| |)的时间逐个更新这些值。算法的时间复杂度为O 插入操作个数 | | 。| |同样是O( )级别的，所以也不能完全解决问题。其实，这里的集合 T 可以理解为我们想维护的询问。我们可以只维护一部分询问中出现的 Y，维护需要的时间就会减少，但是将会有一些询问得不到回答。 1.3 抓住问题的特征得出另一个算法（抓住问题的特征得出另一个算法（算法算法1.2） 为了解决这个问题，我们抓住问题的特征，深入思考。 当遇到一个询问“A Y”的时候，我们要在当前集合 S 中寻找使得 x mod Y

5、 最小的数 x。我们把这里的 x 写成 + ，其中0 ，那么说明区间 , 中没有在 S 中的数，否则 ( )就是区间 , 内的最小数。图1.2 给出了一个具体的例子。 很容易观察到，对很多连续的 a， ( )是相等的。如果 S 为空，则对于任意的自然数 a， ( ) = +。 否则我们把集合 S 中的数排序， 得到 的时候， 的时候，我们继续使用算法1.2；当 的时候我们使用另一种算法。 算法1.2 可以解决大多数 Y 的询问，剩下的 Y 会比较少。回想我们前面提出的算法1.1，当需要维护的 Y 很少时很好。所以当 的时候，我们正好可以使用算法1.1。此时我们令算法1.1 中的集合 T 为1,

6、 ，也就是对1 的询问维护答案。 因此我们得出算法1.3： 首先顺序地处理操作， 回答 的询问。 每次插入对每个1 更新 ( )，需要O( )的时间。回答每个 的询问显然只需O(1)的时间。 然后倒序地处理操作， 回答 的询问。 每次插入操作要把两个集合合并，需要O(1)的时间。 询问A Y时， 我们找O 个区间中的最小数， 对每个区间 , ，我们查找 a 所在的集合， 需要O(1)的时间。 因为 ， 询问的时间复杂度为O 。 算法1.3 的总时间复杂度为O +，其中 K 是一个我们设的边界值。将 N 和 R 看作常数，容易得出当 = 时总时间复杂度最小，为O 。本题中 N 最大 40000，

7、R=500000， 最大约为 28284271，本算法可以完全解决本题。 1.5 小结小结 对这道题， 我们先经过初步思考， 得出了两个朴素算法：算法1.0 和算法1.1。它们在某些输入下会有很好的表现， 但最坏情况下都太慢了， 不能完全解决问题。第 6 页，共 11 页 需要注意的是，其中算法1.1 当| |很小，也就是需要维护的询问很少时，会有很好的表现。 然后我们抓住问题的特征， 由使被一个数除余数最小入手， 得出了算法1.2。算法1.2 当询问中的 Y 比较大的时候比较快，但仍然不能完全解决问题。 算法1.1 和算法1.2 单独使用都不能完全解决问题，但是我们注意到它们可以解决这个问题

8、中两个互补的部分。 我们根据 Y 的大小， 把询问分成两部分处理。对 的询问使用算法1.1，对 的询问使用算法1.2。这样做完全解决了问题。 可见，我们解决本题的重点是，不使用统一的算法，而是同时使用这个问题的两种算法，分别解决问题中的两个互补的部分。 二、问题二二、问题二4 4 2.1 问题描述问题描述 在一个平面上给定 N 个点。 求以这 N 个点中的任意 4 个点为顶点， 可以组成多少个边和坐标轴平行的矩形。 其中1 250000。每个点的时限最多 30s。 2.2 初步分析初步分析 虽然这道题的时限非常长，但 N 最大为 250000。为了解决问题，我们预期要设计出一个时间复杂度低于O

9、( )的算法。 因为组成矩形要求边和坐标轴平行，所以只是需要点的坐标相等，我们只关心坐标的相对关系。所以我们可以把点的坐标离散化。如图 2.1，这样我们会得到一个最坏情况大小N 的网格，输入给定的点分布在网格的格点上。 4 题目来源：MIT Individual Contest 2007，SPOJ RECTANGL 第 7 页，共 11 页 显然，组成矩形的 4 个点会有 2 个点在网格的一行，2 个点在网格的另一行上。因此，我们可以算出网格上每两行点组成的矩形的个数，最后把它们相加即为答案。 2.3 一个不难想到的算法一个不难想到的算法 一个O( )的算法 （算法2.1） 不难想到。 我们分

10、别以网格的每两行 , ( 时， 我们称行 x 为 A 类， 否则为 B 类。 显然问题就被分成了三部分： 1、 以两个 A 类行中的点组成矩形，共有多少个矩形 2、 以两个 B 类行中的点组成矩形，共有多少个矩形 3、 以一个 A 类行和一个 B 类行组成矩形，共有多少个矩形 很容易注意到， A类行的个数必然 ，所以 A 类行中的总点数 = 。而事实上 A 类行中点的个数必然 ，矛盾。 有了 A 类行的个数比较少这个限制，我们就可以对部分 1 使用算法2.1。 注意到算法2.1 中，我们只要先枚举一行，另一行的枚举在时间复杂度上相当于把所有的点都扫描一遍。这就允许我们在处理部分 1 时， “顺

11、便”处理部分3，并且不影响时间复杂度。 而对部分 2，我们有了一个新的限制，即每行中的点数 ，也就是说，每行中的点数会比较少。我们抓住问题的特征，也就是这个限制，设计一个针对每行中点数较少时比较优的算法。 2.5 对部分对部分 2 设计另一个算法（设计另一个算法（算法算法2.2） 部分2中每行中的点数较少也就意味着， 以每行中任意两个不同的点为端点，组成的线段的个数也较少。以一个点作为线段 l 的右端点，因为一行最多有 K 个点，线段 l 的左端点可以有O( )个选择。那么以所有的O( )个点作为右端点，会有O( )条线段。 第 9 页，共 11 页 显然， 将所有的行上的线段放在一起， 对每

12、种线段 , 统计它出现的次数 s。这里的 a 和 b 是指同一行上两个点的列号。容易得出答案就是C 。统计这样的线段出现的次数，很容易想到可以使用 hash，时间复杂度为O( )。但注意到空间复杂度同样为O( )。 不难想到一个减小空间复杂度的方法是：先确定线段的右端点 b，然后将所有右端点为 b 的线段放在一起考虑，把它们的左端点放进 hash。 因为现在只要 hash 一个端点，所以空间被降到了O( )。而每个点和原来一样都只被当作右端点考虑了一次，因此时间复杂度不变，为O( )。 2.6 问题的解决问题的解决 至此 3 个部分都得到了较好的解决，我们将它们合并起来考虑。对部分 1 和部分

13、 3 我们使用算法 2.1，时间复杂度为O 。对部分 2 我们使用算法2.2，时间复杂度为O( )。总时间复杂度为O + 。当 K 取 . 时，时间复杂度达到最小，为O( . )，可以解决本题。 2.7 小结小结 我们经过简单的初步分析后，很轻松地得出了算法2.1。它不能完全解决问题，但当行数比较少的时候会很好。我们根据算法2.1 的这个优势，把问题按每行点数的多少分成了 3 部分。对部分 1 和部分 3 我们是使用算法2.1。而对部分图 2.3：线段2,4出现了 2 次，即图中的两条黑线 第 10 页，共 11 页 2，我们根据它的特征，设计出了一种针对这部分很快的算法2.2。然后我们同时使

14、用算法 2.1 和算法 2.2， 得到了一个总时间复杂度O( . )的算法， 解决了问题。 而假如我们单独使用算法2.1或算法2.2， 都将得到最坏情况下O( )的算法，不能完全解决问题。可见这种算法复合的方法在本题的解决中的重要性。 本题和问题一一样，都是将两种相对简单的算法进行了复合，使用于问题的不同部分，但部分的划分没有上一题那么明显。能这样将问题进行划分，需要我们敏锐的观察力和扎实的基本功。 三、总结 三、总结 一个问题往往可以被看作是由若干个部分组成起来的。注意这里所说的部分是相对并列的。我们通常对这些部分使用统一的算法。而有时这个问题可以使用多种算法解决，并且当这些算法应用在问题中

15、不同特征的部分时，会有不同的效果。这时我们就可以将这些算法复合，对问题的不同部分，根据它们的特征分别选择使用对这个部分较优的算法。这就是本文所讲的算法复合的方法。 对本文中的两个问题，我们都使用了这种方法。问题一中我们得出了两个最坏情况分别是O( )和O( )的算法。它们都不能解决问题，但它们分别针对问题的两个部分会有很好的效果。于是我们对问题的两部分分别使用这两种算法，最终得到了O 的算法，使问题得到了较好的解决。问题二与之类似，我们将两个最坏情况下O( )的算法复合起来，得到了一个O( . )的算法。 我们注意到两个算法合并起来后， 我们很 “神奇” 地得到了一个更优的算法。这是因为这两种

16、算法具有互补的优势，而我们把问题分成了若干部分，对每一部分根据其特征使用较优的算法，就使得两种算法的优势得到了结合。 每个算法都有各自的优势和劣势。 如果我们取长补短， 充分利用它们的优势，也许就将会得出总体更优的算法。这种取长补短的思想是非常重要的。 本文讲的是一类算法复合的方法。作为一种方法，我们在解题时可以选择使用。同时，在解题时不断总结，形成一般性的方法是很重要的。 第 11 页，共 11 页 参考文献参考文献 1 Introduction to Algorithms 作者：Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 2 2005-2007 年国家集训队论文及作业