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<xj，它一定是单调递增的，令k为在二分搜索中将xi和xj分开的最近顶点，则整个二分搜索过程就对应一棵二分搜索树，这个k就代表了二分搜索树中xi和xj的最近公共祖先，i<k<j。因为i和j都是“好”索引，那么xi<xk<xj，这说明xi、xk、xj是有序的，依次类推，对于任何两个好索引，都满足这个性质。因此，如果剩下的序列里面的索引都是好索引，那么它们就都满足这个性质。所以，坏索引的个数如果小于εn，就把这εn个坏索引去掉，剩下的都是好索引，这意味着剩下的都是长度大于等于εn的单调递增的子序列。■
定理2-8 如果输入数列是有序的，算法2-6返回true;如果输入的数组是ε-远离有序，算法2-6返回false的概率大于2/3。
证明 显然，输入数列有序，则每次二分搜索都得到正确的结果，故算法返回true。
根据引理2-4,如果输入ε-远离有序，则存在大于εn个“坏”元素，即数组的每个元素是“坏”元素的概率大于ε。此时，2/ε次挑选的元素都是好的概率小于(1-ε)2/ε<e-2<13，因为选择一个好索引的概率小于1-ε，所有的2/ε个索引都是好的，它的概率就是(1-ε)2/ε，根据前面讲的一个估计是<e-2<13。因此，此时算法返回true的概率小于1/3，所以算法返回false的概率大于2/3。■