《大数据算法》一2.3 时间亚线性判定算法概述
本节书摘来华章计算机《大数据算法》一书中的第2章 ，第2.3节，王宏志 编著, 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
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 全0数组的判定近似算法
1 在A中随机独立抽取s=2/ε个位置上的元素。
2 检查抽样，若不包含1，则输出“是”，若包含1，则输出“否”。
算法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有关。■