转载声明
本文为灯塔大数据原创内容，欢迎个人转载至朋友圈，其他机构转载请在文章开头标注：
转自：灯塔大数据；微信：DTbigdata
编者按：灯塔大数据将每周持续推出《从零开始学大数据算法》的连载，本书为哈尔滨工业大学著名教授王宏志老师的扛鼎力作，以对话的形式深入浅出的从何为大数据说到大数据算法再到大数据技术的应用，带我们在大数据技术的海洋里徜徉~每周五定期更新，欢迎来做客呦！
上期回顾&查看方式：
在上一期中，我们介绍了一类时间亚线性判定算法：全0数组的判定，并且了解了什么是ε-远离的概念，学会了分析其中抽样算法的精确性。在本期中，我们将再讲一个亚线性时间的判定问题——数组有序的判定问题，通过采样的方式访问整个数组的元素，并且详细介绍用来解决数组有序判定问题的经典算法二分查找算法。
PS：了解上期详细内容，请在灯塔大数据微信公众号自定义菜单栏中点击文章精选—文章连载，进行查看。
No.19期 序列有序的判定0 数组的判
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
令k 是在二分搜索中将xi 和xj 分开的最近顶点，也就是对于整个数组建立一个二分搜索树，在二分搜索树中xi 和xj 的最近公共祖先，则i
现在我们回到证明其准确率的问题上。
我们要证明当输入数列ε- 远离有序时，算法返回false 的概率大于2/3。
证明：往证算法返回true 的概率小于1/3。
我们已经证明，如果输入ε- 远离有序，则存在大于εn 个的坏索引，即数组中坏索引的概率大于ε。
当数组中坏索引的概率大于ε时，我们经过了2/ε次选择，每次选择是好索引的概率是1-ε，2/ε都是好索引的概率就是<<。这样算法的精确性也就得到了证明。
小可：嗯，这和全0 数组判定的证明挺像的。
Mr. 王：好了，亚线性算法就讲解到这里，下次课我们来讨论磁盘算法。
下期精彩预告：
经过学习，我们又掌握了亚线性时间的判定问题——数组有序的判定问题，通过采样的方式访问整个数组的元素，并且了解到了用来解决数组有序判定问题的经典算法二分查找算法。
在下一期中，我们将介绍价钱与性能的平衡--磁盘算法，通过建立磁盘模型来更加具体的分析解释磁盘算法。更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！
内容来源：灯塔大数据
【灯塔大数据】微信公众号介绍：中国电信北京研究院通过大数据技术创新，自主研发了业内领先的灯塔大数据行业应用创新平台，灯塔面向市场研究、广告营销、商业地理、金融征信、人力资源等诸多行业领域，提供零售研究、消费者研究、店铺选址、精准营销、泛义征信，背景调查等服务，助力企业在大数据时代扬帆远航。
微信公众号【灯塔大数据】关键字信息：
【六个关键词】 下载运营商大数据PPT
【大数据日】 下载演讲材料
【十月融资】下载2016年10月投融资月报
【网络安全】获取国民网络安全报告全文
【23个理由】下载《大数据让你兴奋的23个理由》电子书
【思维导图】下载12种工具的获取方式
【 灯塔 】 查看更多关键字回复