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

在上一期中，我们介绍了一类时间亚线性判定算法：全0数组的判定，并且了解了什么是“ε-远离”的概念，学会了分析其中抽样算法的精确性。在本期中，我们将再讲一个亚线性时间的判定问题——数组有序的判定问题，通过采样的方式访问整个数组的元素...

转载声明

本文为灯塔大数据原创内容，欢迎个人转载至朋友圈，其他机构转载请在文章开头标注：

“转自：灯塔大数据；微信：DTbigdata”

编者按：灯塔大数据将每周持续推出《从零开始学大数据算法》的连载，本书为哈尔滨工业大学著名教授王宏志老师的扛鼎力作，以对话的形式深入浅出的从何为大数据说到大数据算法再到大数据技术的应用，带我们在大数据技术的海洋里徜徉~每周五定期更新，欢迎来做客呦！

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

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

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

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

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

小可：在这个问题中，ε- 远离有序是怎么定义的呢？

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

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

Mr. 王：的确要通过采样的方式，但是重要的是，对于这个问题我们怎么采样。这里要补充一个预备知识，叫作二分查找算法，这是一个非常经典的算法。利用二分查找法就是希望能在一个递增的序列S 中查找某一个值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 发现ixj 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

    关注 灯塔大数据