《大資料算法》一2.4 數組有序的判定算法

本節書摘來華章計算機《大資料算法》一書中的第2章 ，第2.4節，王宏志　編著, 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

本節讨論數組有序的判定問題的判定算法。

1.問題的定義

數組有序的判定問題

輸入：包含n個數的數組a。

輸出：若a中元素單調遞增則輸出“是”；否則輸出“否”。

首先看一下這個問題的定義，輸出是判定的結果，這個數組是否有序？如果需要精确地回答這個問題，就需要通路n個數，時間是Ω(n)。但是要求是設計亞線性算法，就是不通路所有的資料也能完成判定，是以采用近似算法。

要定義近似，需要用到ε-遠離的概念。在這個問題中，ε-遠離意味着必須删除大于εn個元素才能保證剩下的元素有序。這個問題的近似版本就變成：這個數組有序還是删除大于εn個元素才能保證有序？

2.近似求解

下面說明怎樣設計一個亞線性算法才能解決這個問題。提到亞線性，讀者可能直接想到采取抽樣的方法，這是可以的。但是如何抽樣，如何處理，如何證明抽樣的正确性就不那麼直覺了。算法2-6　數組有序的判定算法

定理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/ε