第2章 时间亚线性算法

顾名思义，时间亚线性算法就是计算时间是亚线性的算法。我们对某些有亚线性运行时间的算法很熟悉，例如，二分查找算法。需要预处理（Ω（n））才能在亚线性时间运行的算法，称为“伪亚线性算法”。在o（n）时间内运行，且不需要对输入预处理的亚线性算法，称为时间亚线性算法，这样的算法不读取全部输入数据，而仅仅读取其中的很小一部分。

2.1 时间亚线性算法概述

本节我们通过两个简单的例子来介绍时间亚线性算法的基本概念。

2.1.1 平面图直径问题的亚线性算法

1．问题的定义

平面图直径问题

输入：有m个顶点的平面图（平面图可以放置在平面上而边不交叉），任意两点之间的距离存储在矩阵D中，即点i到点j的距离为Dij。输入满足如下条件：

1）输入大小是D的大小n=m2。

2）最大的Dij是图的直径。

3）点之间的距离对称且满足三角不等式。距离对称意味着i到j的距离等于j到i的距离；满足三角不等式意味着对于i、j、k来说i到j的距离加上j到k的距离要大于i到k的距离。

输出：该图的直径和距离最大的Dij。

矩阵D可以通过基于动态规划的Floyd算法得到。本小节关心的不是计算D的算法，而是以这个D为输入，计算图的直径和距离最大的Dij。

计算这个问题一个直观的想法是把D遍历一次，从中选择最大的Dij。但是问题没那么简单，如果要求运行时间为o（n），也就是运行时间比输入规模n阶低，应如何处理？

是否能做到呢？想精确完成这个问题是不可能的，因为如果有一个“坏人”知道处理过程，由于时间复杂度为o（n）的算法不可能访问所有的数据，这个“坏人”就让输入中没有访问到的数据中包含最大的。这样处理就会令亚线性方法出错。因而，处理这个问题的时间复杂度应该是O（n）。

本小节将讨论一个亚线性的近似算法，这个算法的计算结果可能不是最好的，但是可以计算出一个和原来的结果相差不多的结果。近似算法的动机就是无法在要求的时间内得到精确解，就退而求其次，求出近似的解。

2．平面图直径问题的近似亚线性算法

该算法仅有两步：第一步，随机选择k≤m。第二步，选择使得Dkl最大的l。也就是说，随机看算法的一行，在这行中找出最大的值作为直径。

下面进行算法的时间复杂度分析，对一个输入为m×m的矩阵，算法只需要访问其中的一行。也就是说输入是m的平方，而算法只需访问其中的m，因此时间复杂度是。

读者会想到上述算法未必得到最优解。确实不一定，但是有了几个输入性质的保证，可以证明该算法在最坏情况下与最优解相差很小，下面的定理说明了这个结论，这意味着即使最坏情况下近似解也不会小于精确解的1/2。

定理2-1 平面图直径问题的亚线性算法的近似比是2。

证明 假设算法的最优解是Dij，那么根据三角不等式，对于选出的k，有Dij≤Dik+Dkj。因为Dkl是所有Dki中的最大值，因此Dik是小于等于Dkl的，Dkj也是小于等于Dkl的。综上所述，

Dij ≤Dik+Dkj ≤Dkl+Dkl ≤2Dkl

因此，Dij小于等于2Dkl，即近似比为2。

2.1.2 排序链表搜索的亚线性算法

排序链表搜索问题

输入：排序双向有序链表R（R中的元素存储在一个无序的队列中），元素x。

输出：如果x在R中，则返回“是”；如果x不在R中，则返回“否”。

问题的目标是确定x是否是输入中给定的n个元素之一。n个元素存储在一个双向链表中，意味着每一个链表中的元素都可以访问它的后一个以及前一个元素，但是链表不能随机访问。表中的元素存放在一个无序队列中，意味着可以根据元素的索引随机访问元素。显然，通过确定性算法不可能在o（n）时间内完成搜索，然而，如果允许随机选择，那么可以在时间内完成搜索。

因为R上仅支持顺序查找，因而该算法的基本思想是找出一个抽样，在抽样中顺序查找x所在的小范围，继而在R中的此范围内顺序查找x。从R中抽样S，在抽样S中找出和x最接近的点p和q，使得x在区间[p, q）之中，接下来仅在R中p和q之间搜索x。由于p和q是以｜R｜/n为概率在S中随机抽样的点且在S中是相邻的，因而S中的元素在区间[p, q）的数学期望是n｜S｜。从而算法的时间复杂度是O（｜R｜+n/｜R｜），为了满足时间复杂度要求，我们取，则算法的时间复杂度可以达到。算法的伪代码如算法2-1所示。

定理2-2证明了该算法执行时间的数学期望是，从而说明了该算法是亚线性算法。

定理2-2 上述算法时间复杂度的数学期望是。

证明 从算法的过程可以看出，算法的运行时间等于+（p,q间元素个数）。由于S包含个元素，R中p,q间元素的个数的期望值为。这表明算法的期望运行时间为。

2.1.3 两个多边形交集问题的多项式时间算法

多边形交集问题

输入：二维空间中两个简单多边形A和B，每个都包含n个顶点。

输出：判断A和B是否相交。这个问题可以在O（n）时间内解决，例如，通过观察，这个问题可以被描述成一个二维线性规划实例，在同样的时间里，可以找到A, B交集中的一点或者找到一条将A, B分隔的直线，该直线包含A和B中各一个点，参见参考文献[1]。

下面我们讨论一个能够达到亚线性的随机算法。这个算法假设多边形A和B的顶点以双向链表的形式存储，每一个顶点都将下一个顶点作为后继，按照顺时针顺序排列。算法的伪代码如算法2-2所示。

显然，算法中第1行的时间复杂度为，第2行可以利用线性时间多项式相交判定算法实现。下面讨论第6行的实现方法和时间复杂度。

令a和b分别是L上A和B的点，a1和a2是A中和a相邻的两个点。我们现在用如下方法定义多边形PA。如果a1和a2中的点都与CA在L的同一侧，那么PA为空。否则，由于a在L上，a1和a2中只可能有一个在CA的另一侧。不失一般性，设此点为a1。沿着a到a1的方向遍历A中的点，直到再次通过L，如图2-1所示。用同样的方法可以生成PB。则PA和PB的大小为，这个结论留给读者证明。

显然A和B相交当且仅当A和PB相交或者B和PA相交。我们仅考虑B和PA相交的判定，A和PB相交的判定方法类似。首先判定CB和PA是否相交，如果相交，则完成判定。否则，生成CB和PA的分隔线LB（通过上述线性算法完成）。接下来，用上述构造的算法递归判定B和PA在LB同一侧的子多边形QB是否和PA相关。于是，B和PA相交当且仅当QB和PA相交。因为QA和PB的期望规模都是，这个判定可以在时间完成。根据上述构造，两个包含n个顶点的多边形相交性判定问题转化为常数个多边形判定问题，每一个的输入规模都是，因而，我们有如下结论。

结论2-1 判断两个n度凸多边形的相交可以在时间内解决。

2.2 最小生成树代价估计

本节讨论最小生成树问题的亚线性算法，首先介绍连通分量个数估计算法，接下来基于此基础算法设计最小生成树代价估计算法。

2.2.1 连通分量个数估计算法

连通分量个数估计问题

输入：一个图G=（V, G），有n个顶点，m条边，该图表示为邻接矩阵，图中结点的最大度为d。

输出：G中连通分量的个数。

这个算法如果用BFS实现，那么每个点的邻居都至少要访问一次，因而精确解的时间复杂度为Ω（dn）。

下面考虑随机化方法。这个算法可以有效地估计连通分量的个数，得到的结果是#CC±εn的概率大于等于2/3，其中#CC是真实连通分量的个数，并且运行时间和n无关。

这个算法的核心思想如下。设C为连通分量的个数，结点u所在连通分量的结点数记作nu, u的权重为1/nu。那么，对于每个连通分量，有。因为nu是连通分量中结点的数量，一个连通分量所有的nu是相等的，而权重1/nu的点的个数就是这些点对应的连通分量中点的个数n u，即1/nu ×nu=1。（同样的思想在参考文献[12]中35.3节的最小集合覆盖近似算法的近似比证明里用到过。）对每一个连通分量而言，它所对应的顶点的1/nu之和是1，那么所有顶点的1/nu之和就是图中连通分量的个数。

这样就把这个问题转化为怎样快速地估计nu。显然，可以通过抽样来快速估计nu和1/nu的和，即用少部分点来表示这个和。

这个估计问题并不能通过直接的抽样和估计来解决。考虑一个很坏的情况：所有的顶点都在一个连通分量中。这种情况下计算nu需要一次BF S，时间复杂度是O（m），从而导致了算法不是亚线性的。

我们基于下面的想法来估计nu的值：如果u所在的连通分量结点数很少，其规模可以通过BF S直接估计；如果u所在的连通分量很大，那么1/nu就很小，这意味着它对整个和的贡献很小，因此可以在几步内完成BFS，完成不了的点就放弃，因为它对和的贡献足够小。

根据上述讨论，对这个问题可以做这样的估计，即估计值。当连通分量不大时，是BFS可以准确算出的nu；如果连通分量大于阈值2/ε，就取等于2/ε。

引理2-1描述了这个估计的误差界限。

引理2-1 对于图G=（V, E）, ，则。

证明 对于点u来说，连通分量结点数量小于2/ε时，估计值等于真实值，即 。当u所对应的连通分量结点数量大于等于2/ε时，误差。因而。

根据上述讨论，算法描述如算法2-3所示。

算法的时间复杂度和精度分别如定理2-3和定理2-4所示。

定理2-3 算法2-3的运行时间是。

证明 根据算法运行过程可知，算法循环的轮数和同阶。在每一循环中最多处理结点的个数是2/ε。那么处理每个结点需要从这个结点开始做BFS，最多访问2/ε个结点。在BFS过程中，从每个结点出发都要访问其所有邻居，因此，每轮的代价是d/ε。此外，还需要将其存到排序序列L中。由于L需要有序，可以用一个平衡二叉树保存L。考虑到插入和删除一个元素到一个具有2/ε个结点的平衡二叉树的代价为log2/ε，运行时间是。

从定理2-3可以看出，该算法的运行时间和整个图的大小没有关系，只和输入的ε和顶点的度d有关系。

定理2-4有n个顶点的图G中，若其顶点的度至多为d，算法2-3对G中连通分量个数的估计误差最多为±εn的概率大于2/3，即，其中C是G中连通分量的个数。

证明 对于算法2-3抽样中的第i个结点u，令。对于整个抽样来说，令Y等于所有的Yi相加，即。由于所有的结点都是独立抽样的，因而所有的E（Yi）都等于E（Y1），故。

根据上述讨论可知, 的数学期望为。因此，

根据Hoeffding不等式，。因为s和同阶，因此，取s=4/ε2，则

，根据引理2-1,，则 。因而。

2.2.2 最小生成树代价估计算法

1．问题的定义

输入是无向有权连通图G=（V, E），其顶点的度最大为D，边上的权来自整数集合{1,2,3, …, W}，最大不超过W，令一棵生成树的代价定义为这棵树上所有边的权重之和，问题的输出是图G的最小生成树的代价。最小生成树的例子如图2-2所示，左图是原图，其最小生成树如右图所示，它的代价是26。

求最小生成树的精确算法是贪心法，可以用Prim算法或Kruskal算法。其时间复杂度为O（mlogn），是超过线性的。本小节研究求最小生成树代价的时间亚线性算法。

2．亚线性算法思想

在设计算法的过程中，有两个假设。第一个假设是图组织成邻接表的形式，这意味着可以直接访问每个结点的所有邻居。第二个假设是可以随机均匀地选择结点，这保证了可以随机均匀抽样。

时间亚线性算法的基本思想是利用特定子图连通分量的数量估计最小生成树的权重。这有一些抽象，看一个具体的例子。假设一个简单图G，所有边的权重都是1或者2，我们考虑将最小生成树的权重用权重为1和2的边分别表示。

首先，所有的边都是大于等于1的，把所有边的权重都减去1，这时对于最小生成树，权重减掉了n-1，即权重至少为1的边的数量。剩下图中最小生成树的边数等于最小生成树中权重大于1的边的数量，因为所有边的权重减去1意味着剩下边的权重在原来的图中是2，在最小生成树中把减掉的权重加回来就得到了整个最小生成树的权重。因而这个最小生成树的权重表示为#N1+#N2（#Ni：最小生成树中权重至少为i的边的数量）, #N1=n-1。

下面讨论#N2的计算方法。考虑这样一件事情，把最小生成树中所有边的权重减掉1，剩下的就是原来权重是2的边。如果在最小生成树当中把这些权重是2的边都去掉，则最小生成树会变成若干个连通分量。那么，剩下的连通分量中每条边的权重都是1，这时生成的图变得不连通。最小生成树需要把整个图的所有点都连上，这就需要这些最小生成树当中权重为2的边来连接。那么，最小生成树当中权重为2的边的数量就等于把这些连通分量连到一起所需要的边数，即至少是这些连通分量的个数减去1。因此，#N2就是权重为1的边构成的导出子图的连通分量数减去1。

依次类推，如果这个图的权重有1,2,3 三种，那么，#N3就是去掉权重为3的边以后，在边的权重只是1和2的情况下，构成的导出子图中连通分量数减去1。

引理2-2描述了一般情况下最小生成树和连通分量的关系。

引理2-2 设Gi是G中包含所有权重小于i的边的子图，Ci是Gi中的连通分量个数，那么最小生成树中权重大于i的边数为Ci-1。因此最小生成树的权重为

证明 令βi为最小生成树中权重大于i的边的个数，每条边对最小生成树的权重的基础贡献为1，每条权重大于1的边额外贡献了1，每条权重大于2的边贡献的更多，因此

其中C0是把所有边都去掉剩下的连通分量数量，即n。

3．算法的描述

引理2-2把最小生成树的权重和子图的连通分量个数联系到一起。现在的问题转化为给定一个图，怎样快速地估计图中连通分量的数量，如果能够快速估计出连通分量的数量，则能够有效估计出最小生成树的权重。根据2.2.1节中的讨论，最小生成树代价估计算法如算法2-4所示，其中用于估计G中包含所有权重小于i的边的子图Gi中的连通分量个数，其输入中的是一个参数，该参数用于在计算连通分量过程中控制从每个点开始进行BFS所访问的最多顶点，即。

算法2-4的时间复杂度，是前面讲过的估计连通分量算法的复杂度和W的乘积，显然和图中顶点的个数无关。

下面分析该算法的误差，由于表示W-1个连通分量权重的累加，根据定理2-4，对每个，满足，而要使有界限，需要所有W-1个都满足，此事件概率的下界是（2/3）W-1，并不能保证常数界限，因而需要在求连通分量个数的函数中设置合适的抽样次数，以降低发生概率的上界。

引理2-3 在估计连通分量个数算法2-3中，抽样次数，则对计算过程中的每个连通分量C都满足。

证明 考虑定理2-4的证明，取，由公式（2-1）和（2-2），有

根据引理2-1的证明过程，取时，，故。

定理2-5 算法2-4得到的结果和WMST的误差满足。

证明 根据引理2-3，对于每个Ci都满足，从而，根据并集界限，即若干事件都发生的概率小于等于它们单独发生的概率之和：

4．乘近似

注意定理2-5求出来的是误差的界限，即估计值和真实值之间的差，但在有些情况下需要这种乘的近似比，即估计值和真实值之间的比值。可以根据定理2-5中的差推出比值，如推论2-1所示。

推论2-1 算法2-4得到的估计值满足。

证明 MST的代价是WMST≥n-1，因此当n≥2时，WMST≥n/2。在定理2-5中，。因此，，故（1-2ε）。根据定理2-5, 。

上述推论说明了这个算法是（1 ±2ε）近似的。

2.3 时间亚线性判定算法概述

本节将介绍时间亚线性判定算法。顾名思义，时间亚线性判定算法指的是在输入的亚线性时间完成判定任务的算法。在很多情况下，判定问题无法在要求的时间内得到精确解，需要寻找近似解。

1．ε-远离

我们来看一个例子，考虑图2-3中哪些图片是“猫”。可以看到第一幅和第四幅图片毫无疑问是猫，第二幅图片里面只有汽车，但是第三幅图片就不确定了，里面放只机器猫，并不容易判定是否真的是猫。上述例子代表了判定问题的三种情况：满足待判定性质、远非满足待判定性质和差不多满足待判定性质。当然，可以说“差不多满足待判定性质”或“差不多不满足待判定性质”。

根据上述讨论，判定问题的精确解是严格地判断输入是“满足命题”还是“不满足命题”；而判定问题的近似解仅需要区分输入是“满足命题”还是“与命题相差很远”就可以，对于差不多的情况，则不做区分。这里涉及一个问题：如何定义“与命题相差很远”？可以按照如下方式定义。

定义2-1（ε-远离）对于命题L和输入x，如果从x到L中任意字符串的汉明距离至少为ε｜x｜，则x是ε-远离L的。

定义2-1是从计算理论的角度定义的，x是字符串集合，L是一个语言，用于描述一个命题。对于具体的问题，ε-远离有不同的定义方法，下面来看一个实例。

2．全0数组判定问题的亚线性时间算法

全0数组判定问题

输入：包含n个元素的0,1数组A。

输出：如果A中的元素全是0则输出“是”；如果A中的元素有1则输出“否”。

这是一个很简单的问题，很自然会想到把里面的数字全部扫描一遍就可以，但是亚线性时间算法要求的运行时间是n的严格低阶函数o（n）。

这个问题的时间复杂度的下界应该是n，因为如果算法访问的数量少于n的话，一定存在没有访问到的数字。因此，可以扮演一个“坏人”，把这个算法访问不到的数字设为1，这样就会让算法出现误报。

由于无法设计亚线性精确算法，就需要考虑设计近似算法。这里，我们用上述ε-远离的概念定义近似程度。首先，对于全0数组判定问题的ε-远离定义如下：

数组含1的个数大于εn，即为ε-远离。

根据这个ε-远离，全0数组判定问题的判断就变成了是否A=00…0或者A中包含1的个数大于εn。

可以设计基于抽样的算法，伪代码如算法2-5所示。

算法2-5的时间复杂度是O（s），和n无关，因而是一个亚线性算法。

但该算法显然会出现误判，因为如果一些1没有被抽出来，那么就会出现假阳性——判断的结果为是，但实际为否。但如定理2-6所示，结果并没有那么坏，也就是说出现这个情况的概率不是很大。

定理2-6 如果A是全0数组，始终输出“是”; A是ε-远离时，出错的概率是小于1/3的。

证明 显然，如果A是全0数组，其抽样一定全都是0，则必然输出“是”。只有A中包含1，但是没有被抽样抽出来的时候算法才会出现错误。下面分析出错的概率。如果A是ε-远离的，意味着A中1的个数是大于等于εn的，也就是说随机抽出一个数，其是1的概率大于ε，是0的概率就小于等于1-ε。从这个角度来看，当A是ε-远离时出错的概率也就意味着抽样中没有1的概率，这就需要计算抽出的样本全部是0的概率，因为任意一个样本是0的概率小于等于1-ε，则s个抽样全都是0的概率小于（1-ε）s，即

因此，当A是ε-远离时，出错的概率是小于1/3的。

也就是说数组全是0，可以100%地准确区分；当ε-远离的时候，出错的概率很小。因此，这个算法可以达到近似计算的目的。而运行时间很显然和数组的长度没有关系，仅和抽样的个数s有关。

2.4 数组有序的判定算法

本节讨论数组有序的判定问题的判定算法。

1．问题的定义

数组有序的判定问题

输入：包含n个数的数组A。

输出：若A中元素单调递增则输出“是”；否则输出“否”。

首先看一下这个问题的定义，输出是判定的结果，这个数组是否有序？如果需要精确地回答这个问题，就需要访问n个数，时间是Ω（n）。但是要求是设计亚线性算法，就是不访问所有的数据也能完成判定，所以采用近似算法。

要定义近似，需要用到ε-远离的概念。在这个问题中，ε-远离意味着必须删除大于εn个元素才能保证剩下的元素有序。这个问题的近似版本就变成：这个数组有序还是删除大于εn个元素才能保证有序？

2．近似求解

下面说明怎样设计一个亚线性算法才能解决这个问题。提到亚线性，读者可能直接想到采取抽样的方法，这是可以的。但是如何抽样，如何处理，如何证明抽样的正确性就不那么直观了。

定理2-7和定理2-8分别描述了该算法的时间复杂度和精度。

定理2-7 算法2-6是亚线性算法。

证明 算法2-6的时间复杂度是2/ε乘以二分查找的代价O（logn），即，该时间复杂度是logn多项式，因而算法2-6是亚线性算法。

引理2-4 如果“坏”索引的个数小于εn，则其存在一个长度大于εn的单调递增子序列。

证明 往证如果在数组中把坏索引去掉，那么剩下的序列一定是单调递增子序列。因为对于任意“好”索引i和j, xi＜xj，它一定是单调递增的，令k为在二分搜索中将xi和xj分开的最近顶点，则整个二分搜索过程就对应一棵二分搜索树，这个k就代表了二分搜索树中xi和xj的最近公共祖先，i＜k＜j。因为i和j都是“好”索引，那么xi＜xk＜xj，这说明xi、xk、xj是有序的，依次类推，对于任何两个好索引，都满足这个性质。因此，如果剩下的序列里面的索引都是好索引，那么它们就都满足这个性质。所以，坏索引的个数如果小于εn，就把这εn个坏索引去掉，剩下的都是好索引，这意味着剩下的都是长度大于等于εn的单调递增的子序列。

定理2-8 如果输入数列是有序的，算法2-6返回true；如果输入的数组是ε-远离有序，算法2-6返回false的概率大于2/3。

证明 显然，输入数列有序，则每次二分搜索都得到正确的结果，故算法返回true。

根据引理2-4，如果输入ε-远离有序，则存在大于εn个“坏”元素，即数组的每个元素是“坏”元素的概率大于ε。此时，2/ε次挑选的元素都是好的概率小于，因为选择一个好索引的概率小于1-ε，所有的2/ε个索引都是好的，它的概率就是（1-ε）2/ε，根据前面讲的一个估计是。因此，此时算法返回true的概率小于1/3，所以算法返回false的概率大于2/3。

2.5 串相等判定算法

本节讨论一个通信亚线性算法问题，因为在很多情况下，数据传输时间和数据量大致成正比，因而将通信亚线性算法归到本章讨论。

在现实中会有这样的问题，假设A公司总部有一个庞大的数据库，而在分公司B处保存这个数据库的副本，为了数据库的一致性，要定期地比较数据。这就涉及串相等判定问题。

串相等判定问题

输入：串s1和s2。

输出：如果s1=s2输出“是”，如果s1≠s2输出“否”。

很显然，任何一致性检测都要求发送所有n位数据，否则，无法检测未发送位置的错误。但是，对于庞大的数据库，n可能非常大，传输全部n位几乎不可能。

设将s1中的n位数据表示为（a1, …, an）, s2中的n位数据表示为（b1, …, bn），一个可能的方法是随机选一些位，然后对随机选择的位进行判断。这样做的问题在于，如果产生的错误在总的串中比例很小（比如仅有一个错误），则这种方法将失效。因而需要具有全局性的方法。

基本想法是为两个字符串制作指纹来体现字符串的全局特征，即我们将数据看成n位的整数a和,，定义指纹函数（p为素数）:Fp（x）=x modp。

算法是随机选取素数p，检测Fp（a）=Fp（b）是否成立。

下面讨论p的选取对算法的影响。

根据这个算法，在计算过程中，需要比较的数字最大不超过p，因而需要传输logp位，而不是n位。考虑到传输效率的问题，希望选择一个较小的p。

下面讨论算法的误判概率，在a和b不等且都与p同余的情况下会发生假阳性的误判。

设c=｜a-b｜，也就是，当a≠b且c整除p时发生误判。由于c≤2n, c的素因子至多有n个。给定一个p，通过素数定理，大概有p/ln（p）个小于p的素数，此时出错的概率是nlnp/p。

根据上述讨论，现在我们想选择一个素数p，这个数字要足够大以确保有足够多小于p的素数，同时这个数字又要足够小以确保高效的通信。

取p=2n2ln（n）（取这个数是为了计算方便，但这样的p可能不是一个整数，在实际实现中可以取p是一个大于2n2ln（n）但和2n2ln（n）最接近的素数），代入出错概率公式，发生错误的概率不超过2/n，在这种情况下需要传输的位数为O（logn）。

习题

2.1 证明2.1.3节中生成的多边形PA和PB包含点的个数为。

2.2 为了保障航运安全，旅客不允许携带危险品乘坐飞机，因此在旅客登机前需要由安检人员检测旅客是否携带危险物品。假设共有n名旅客需要登机，用o（n）时间近似判断这n名旅客是否有人携带危险品。

2.3 在输入的正文串（长度为n）中查找某一字符是否出现，若出现，输出1，否则输出0。设计时间复杂度为o（n）的算法求解这个问题。

2.4 miRNA（微小RNA）在生命活动中具有重要功能，由约21 个碱基构成，比如AU-GUCCUCCUUAUGCCUAUGC可能就是一条miRNA。如果我们想知道细胞内有没有感兴趣的miRNA，可以通过测序解决。测序结果可能是n个21 碱基的序列。设计时间复杂度为o（n）的算法，给定包含n个测序结果的集合S（n条序列）和感兴趣的miRNA序列l，判定S是否包含l。

2.5 一幅二值图（有n个像素）仅由0和1 组成，设计时间复杂度为o（n）的算法，判断该图的黑色（1）和白色（0）是否各占一半。

2.6 设计亚线性算法检查两个字符串是否相同。

2.7 设计时间复杂度为o（n）的算法，判断一个包含n个数的数组是否有相同的数字。

2.8 设计时间复杂度为o（n）的算法，判定输入规模为n的0,1 数组中，是否正好有k（k≤n）个0。

2.9 设计时间复杂度为o（n）的算法，判定一个长度为n的0,1 数组是否为0,1 交替的循环数组。