828
《大數據算法》一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<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。■
最後更新：2017-06-21 13:01:57