《大数据算法》一2.4 数组有序的判定算法
本节书摘来华章计算机《大数据算法》一书中的第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<j 但是xi>xj then //碰到了“坏”索引
return false
return 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/ε