562      阿裏雲  技術社區[雲棲]

《大數據算法》一2.3　時間亞線性判定算法概述

本節書摘來異步社區《大數據算法》一書中的第2章 ，第2.3節，王宏誌　編著, 更多章節內容可以訪問雲棲社區“異步社區”公眾號查看。

2.3　時間亞線性判定算法概述

本節將介紹時間亞線性判定算法。顧名思義，時間亞線性判定算法指的是在輸入的亞線性時間完成判定任務的算法。在很多情況下，判定問題無法在要求的時間內得到精確解，需要尋找近似解。
1.ε-遠離
我們來看一個例子，考慮圖2-3中哪些圖片是“貓”。可以看到第一幅和第四幅圖片毫無疑問是貓，第二幅圖片裏麵隻有汽車，但是第三幅圖片就不確定了，裏麵放隻機器貓，並不容易判定是否真的是貓。上述例子代表了判定問題的三種情況：滿足待判定性質、遠非滿足待判定性質和差不多滿足待判定性質。當然，可以說“差不多滿足待判定性質”或“差不多不滿足待判定性質”。

根據上述討論，判定問題的精確解是嚴格地判斷輸入是“滿足命題”還是“不滿足命題”；而判定問題的近似解僅需要區分輸入是“滿足命題”還是“與命題相差很遠”就可以，對於差不多的情況，則不做區分。這裏涉及一個問題：如何定義“與命題相差很遠”？可以按照如下方式定義。
定義2-1(ε-遠離)　對於命題L和輸入x，如果從x到L中任意字符串的漢明距離至少為εx，則x是ε-遠離L的。
定義2-1是從計算理論的角度定義的，x是字符串集合，L是一個語言，用於描述一個命題。對於具體的問題，ε-遠離有不同的定義方法，下麵來看一個實例。
2.全0數組判定問題的亞線性時間算法
全0數組判定問題
輸入：包含n個元素的0,1數組A。
輸出：如果A中的元素全是0則輸出“是”；如果A中的元素有1則輸出“否”。
這是一個很簡單的問題，很自然會想到把裏麵的數字全部掃描一遍就可以，但是亞線性時間算法要求的運行時間是n的嚴格低階函數o(n)。
這個問題的時間複雜度的下界應該是n，因為如果算法訪問的數量少於n的話，一定存在沒有訪問到的數字。因此，可以扮演一個“壞人”，把這個算法訪問不到的數字設為1，這樣就會讓算法出現誤報。
由於無法設計亞線性精確算法，就需要考慮設計近似算法。這裏，我們用上述ε-遠離的概念定義近似程度。首先，對於全0數組判定問題的ε-遠離定義如下：
數組含1的個數大於εn，即為ε-遠離。
根據這個ε-遠離，全0數組判定問題的判斷就變成了是否A=00…0或者A中包含1的個數大於εn。
可以設計基於抽樣的算法，偽代碼如算法2-5所示。算法2-5　全0數組的判定近似算法

1　　在A中隨機獨立抽取s=2/ε個位置上的元素。
2　　檢查抽樣，若不包含1，則輸出“是”，若包含1，則輸出“否”。

算法2-5的時間複雜度是O(s)，和n無關，因而是一個亞線性算法。
但該算法顯然會出現誤判，因為如果一些1沒有被抽出來，那麼就會出現假陽性——判斷的結果為是，但實際為否。但如定理2-6所示，結果並沒有那麼壞，也就是說出現這個情況的概率不是很大。
定理2-6　如果A是全0數組，始終輸出“是”;A是ε-遠離時，出錯的概率是小於1/3的。
證明　顯然，如果A是全0數組，其抽樣一定全都是0，則必然輸出“是”。隻有A中包含1，但是沒有被抽樣抽出來的時候算法才會出現錯誤。下麵分析出錯的概率。如果A是ε-遠離的,意味著A中1的個數是大於等於εn的，也就是說隨機抽出一個數，其是1的概率大於ε，是0的概率就小於等於1-ε。從這個角度來看，當A是ε-遠離時出錯的概率也就意味著抽樣中沒有1的概率，這就需要計算抽出的樣本全部是0的概率，因為任意一個樣本是0的概率小於等於1-ε，則s個抽樣全都是0的概率小於（1-ε）s,即因此，當A是ε-遠離時，出錯的概率是小於1/3的。
也就是說數組全是0，可以100%地準確區分；當ε-遠離的時候，出錯的概率很小。因此，這個算法可以達到近似計算的目的。而運行時間很顯然和數組的長度沒有關係，僅和抽樣的個數s有關。■

最後更新：2017-06-21 13:01:57

  上一篇：  《大數據算法》一2.4　數組有序的判定算法

  下一篇：  《大數據算法》一2.2　最小生成樹代價估計