每周学点大数据 | No.19全0 数组的判定

No.19期

全0 数组的判定

Mr. 王：接下来我们讲一类时间亚线性判定算法，先来举个例子吧。假设有一个数组A，其中包含0 和1，我们需要判定数组里面的元素是否全是0，如果全是0，则输出“是”；否则输出“否”。依然要求时间复杂度为o(n)。

小可：还是一样访问不到所有的数据啊，可是这回不一样了。在最优化问题中，虽然得不到最优解，但是可以返回一个近似解，只要知道这个近似解和最优解差多少就可以了。这种判定问题只有一个是或者否，如果还是差不多的话，岂不是答错了吗？

Mr. 王：对于判定问题，则换了一种近似的方法，我们的回答是输入满足某种性质，或者远非满足某种性质。

小可：远非满足？

Mr. 王从抽屉里拿出了几张图片，一张画着猫，一张画着汽车，一张画着猫头鹰。

猫和远非猫 1

Mr. 王：你看看这几张图片，假设我们的算法是要识别某张图片里面是不是画着猫。第一张图片没什么说的，它一定满足有猫这个性质；第二张图片里面画着汽车，这就是远非满足有猫这个性质；而第三张图片就比较复杂了，里面画着猫头鹰，这需要算法仔细地进行判断，而这种判断需要消耗的时间就会比较长，如果时间条件要求比较苛刻，我们就真可能将其判断为有猫了。对于判定问题的严格精确解，我们能给出严格的是或者否；而对于判定问题的近似算法，只要给出“是”和“差得很远”这两种情况就可以了；对于那种“差不多”的情况我们不做区分。在上面的例子中，近似算法只要能够找出猫就可以了，对于猫头鹰，我们可以不做区分。

小可：嗯，但是怎么定义这个“差得很远”和“差不多”呢？

Mr. 王：这里提出一个概念叫作“ε- 远离”。对于输入字符串x，如果从x 到字符串集合L中任意字符串的汉明距离至少为ε|x|，则x 是ε- 远离L 的。

Mr. 王：那么你来想想，这个问题应该怎么解决呢？

小可：既然处理不了所有的元素，那么只要挑出一部分来看看它们是不是0 就可以了，这就是抽样！

Mr. 王：很好，就是利用抽样算法，具体算法是这样的：

（1）在A 中随机独立抽取s=2/ε 个位置上的元素。

（2）检查抽样，若不包含1，则输出“是”；若包含1，则输出“否”。

小可：嗯，抽取这个特殊的数量有什么含义呢？

Mr. 王：我们就来分析一下这个算法的精确性。当数组中包含1 却没有被抽取出来时，算法就会出现误报，这种本来应该返回否而算法返回是的情况，我们称作假阳性。如果A 是ε-远离的，那么误报的概率就是：

这是为什么呢？我们每次抽取到1 的概率是ε，那么抽取到0 的概率就是1-ε，最后抽取s次每次都抽取到0 的概率就是(1-ε)s，后面的部分是概率统计中的近似结论，了解即可。

小可：而且这个算法的运行时间还与数组的长度无关，仅跟抽样次数s 有关，时间复杂度就是O(s)，而s 是远小于A 的长度的，所以它是一个时间亚线性算法。

Mr. 王笑着说：很好，分析得很对。下面再给出一个证据引理：

如果一次测试以大于等于p 的概率获得一个证据，那么s=2/p 轮测试得到证据的概率大于等于2/3。

对于判定问题L，其查询复杂性为q(n) 和近似参数ε 的性质测试算法是一个随机算法，其满足对于给定L 的是一个实例x，最多进行q(|x|) 次查询，并且满足下述性质：

• 如果x 在L 中，该算法以最小2/3 的概率返回“是”。
• 如果x 是ε- 远离L 的，该算法以最小2/3 的概率返回“否”。

内容来源：灯塔大数据