本节书摘来华章计算机《大数据算法》一书中的第2章 ，第2.4节，王宏志　编著, 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.4　数组有序的判定算法

本节讨论数组有序的判定问题的判定算法。

1.问题的定义数组有序的判定问题输入：包含n个数的数组A。输出：若A中元素单调递增则输出“是”；否则输出“否”。首先看一下这个问题的定义，输出是判定的结果，这个数组是否有序？如果需要精确地回答这个问题，就需要访问n个数，时间是Ω(n)。但是要求是设计亚线性算法，就是不访问所有的数据也能完成判定，所以采用近似算法。要定义近似，需要用到ε-远离的概念。在这个问题中，ε-远离意味着必须删除大于εn个元素才能保证剩下的元素有序。这个问题的近似版本就变成：这个数组有序还是删除大于εn个元素才能保证有序？2.近似求解下面说明怎样设计一个亚线性算法才能解决这个问题。提到亚线性，读者可能直接想到采取抽样的方法，这是可以的。但是如何抽样，如何处理，如何证明抽样的正确性就不那么直观了。算法2-6　数组有序的判定算法

for k=1 to 2/ε do　　选择数组中第i个元素xi　　用xi在数组中做二分查找　　if发现i
    
     xj　then　//碰到了“坏”索引　　　　return falsereturn true
    

定理2-7和定理2-8分别描述了该算法的时间复杂度和精度。

定理2-7　算法2-6是亚线性算法。证明　算法2-6的时间复杂度是2/ε乘以二分查找的代价O(logn)，即O2εlogn，该时间复杂度是logn多项式，因而算法2-6是亚线性算法。■引理2-4　如果“坏”索引的个数小于εn,则其存在一个长度大于εn的单调递增子序列。证明　往证如果在数组中把坏索引去掉，那么剩下的序列一定是单调递增子序列。因为对于任意“好”索引i和j，xi定理2-8　如果输入数列是有序的，算法2-6返回true;如果输入的数组是ε-远离有序，算法2-6返回false的概率大于2/3。证明　显然，输入数列有序，则每次二分搜索都得到正确的结果，故算法返回true。根据引理2-4,如果输入ε-远离有序，则存在大于εn个“坏”元素，即数组的每个元素是“坏”元素的概率大于ε。此时，2/ε次挑选的元素都是好的概率小于(1-ε)2/ε