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

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. 王：好了，亚线性算法就讲解到这里，下次课我们来讨论磁盘算法。

内容来源：灯塔大数据