每周学点大数据 | 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 的概率返回“否”。

内容来源:灯塔大数据

本文分享自微信公众号 - 灯塔大数据(DTbigdata)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-12-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端桃园

知识体系解决迷茫的你

最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

22340
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

18230
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

30140
来自专栏钱塘大数据

中国互联网协会发布:《2018中国互联网发展报告》

在2018中国互联网大会闭幕论坛上,中国互联网协会正式发布《中国互联网发展报告2018》(以下简称《报告》)。《中国互联网发展报告》是由中国互联网协会与中国互联...

13750
来自专栏腾讯高校合作

【倒计时7天】2018教育部-腾讯公司产学合作协同育人项目申请即将截止!

16020
来自专栏钱塘大数据

理工男图解零维到十维空间,烧脑已过度,受不了啦!

让我们从一个点开始,和我们几何意义上的点一样,它没有大小、没有维度。它只是被想象出来的、作为标志一个位置的点。它什么也没有,空间、时间通通不存在,这就是零维度。

34530
来自专栏怀英的自我修炼

考研英语-1-导学

英二图表作文要重视。总体而言,英语一会比英语二难点。不过就写作而言,英语二会比英语一有难度,毕竟图表作文并不好写。

12110
来自专栏腾讯社交用户体验设计

ISUX Xcube智能一键生成H5

51420
来自专栏微信公众号:小白课代表

不只是软件,在线也可以免费下载百度文库了。

不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

44730
来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.2K20

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励