首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每周学点大数据 | No.20序列有序的判定

每周学点大数据 | No.20序列有序的判定

作者头像
灯塔大数据
发布2018-04-08 16:25:59
6460
发布2018-04-08 16:25:59
举报
文章被收录于专栏:灯塔大数据灯塔大数据

No.19期

序列有序的判定0 数组的判

Mr. 王:这里我们再讲一个亚线性时间的判定问题——数组有序的判定问题。你来说一下问题定义,并想一想这个问题的精确解。

小可:输入:n 个数的数组,x1, x2,…, xn。

输出:如果数组有序则返回“是”,否则返回“否”。

如果是求精确解的话,需要逐个元素与后面的元素进行比较,一旦发现有逆序的情况,返回否就可以了。可是这样做的时间复杂度是W(n),当数据有很多的时候,这个算法是不适用的。

Mr. 王:很好,现在你分析问题已经很成熟了。这里同样要提出一个近似判定算法。我们要确定的是,这个数组是有序的,还是ε- 远离有序的。

小可:在这个问题中,ε- 远离有序是怎么定义的呢?

Mr. 王:在此问题中,如果删除数组中多于εn 个的元素会使数组有序,我们就称这个数组为ε- 远离有序的。这意味着问题变成了,数组是有序的,还是要删除数组中多于εn 个的元素才能使之有序的判定问题。

小可:既然不能访问整个数组中的元素,那么我们还是以采样的方式来进行吗?

Mr. 王:的确要通过采样的方式,但是重要的是,对于这个问题我们怎么采样。这里要补充一个预备知识,叫作二分查找算法,这是一个非常经典的算法。利用二分查找法就是希望能在一个递增的序列S<x1,x2,x3,…,xn> 中查找某一个值x。

具体的做法是这样的:首先找到S 的中位数mid,然后与x 进行比较,如果x=mid,直接返回位置就可以了;如果x>mid,就把新的查找区间定为(mid,xn),否则定为(x1,mid) ;依此类推,直到查找到x 的位置。

二分查找的时间复杂度是对数时间的,也就是O(logn)。这里我们先对其进行简单的解释,后面会详细地根据有根树的性质讨论它的复杂度问题。这相当于我们在一棵“二分搜索树”上进行查找操作。

算法的第1 步,我们面对的是整个数据序列,所选择的数字是比中位数小还是比中位数大,这样相当于将整个序列划分为两部分,一部分是比中位数小的一半,另一部分是比中位数大的一半。

第2 步,数据集合中只剩下了我们要访问的一半,再从这一半中找到一半。好了,我们回到数组有序判定这个问题上,来看看下面这个算法:

1 for k=1 to 2/ε do

2 随机选择数组中第i 个元素xi

3 用xi 在数组中做二分查找

4 if 发现i<j,但是xi>xj then // 碰到了“坏”索引

5 return false

6 return true

算法的第4 行表示,一旦发现两个数前面的比后面的小,就说明这个数组是无序的,我们称之为“坏”索引。这个算法的时间复杂度为O ( log n)_ ,因为外面的循环执行了次,2 是常数c 就可以忽略了。至于后面的logn,是因为二分查找的时间复杂度是logn。Logn的阶是要比n低的,即logn=o(n),说明这是一个亚线性算法。

小可:这个算法的准确度如何呢?

Mr. 王:如果输入的数组是有序的,那么一定会返回“是”。我们要证明的就是,对于一个ε-远离的数组,准确率可以达到。

小可:我想起了全0 数组的判定问题。

Mr. 王:差不多。首先回忆一下我们前面讲过的证据引理。我们来证明这么一个问题:如果输入ε- 远离有序,则存在大于εn 个的“坏”索引,也就是前面算法中提到的逆序。

证明:一个命题和它的逆否命题同真假,我们不妨来证明它的逆否命题,就是如果“坏”索引的个数小于εn,则其存在一个长度大于εn 的单调递增的子序列。我们可以考虑,如果“坏”索引都被剔除的话,留下的就是一个单调递增的子序列了。

对于任意“好”索引i 和j,有xi<xj。

令k 是在二分搜索中将xi 和xj 分开的最近顶点,也就是对于整个数组建立一个二分搜索树,在二分搜索树中xi 和xj 的最近公共祖先,则i<k<j,因为i 和j 都是“好”索引,那么xi<xk<xj。

现在我们回到证明其准确率的问题上。

我们要证明当输入数列ε- 远离有序时,算法返回false 的概率大于2/3。

证明:往证算法返回true 的概率小于1/3。

我们已经证明,如果输入ε- 远离有序,则存在大于εn 个的“坏”索引,即数组中“坏”索引的概率大于ε。

当数组中“坏”索引的概率大于ε时,我们经过了2/ε次选择,每次选择是“好”索引的概率是1-ε,2/ε都是“好”索引的概率就是<<。这样算法的精确性也就得到了证明。

小可:嗯,这和全0 数组判定的证明挺像的。

Mr. 王:好了,亚线性算法就讲解到这里,下次课我们来讨论磁盘算法。

内容来源:灯塔大数据

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2016-12-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 灯塔大数据 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
大数据
全栈大数据产品,面向海量数据场景,帮助您 “智理无数,心中有数”!
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档