亞時間線性算法

圖直徑問題

定義：m個頂點的圖，任意兩點的距離儲存在矩陣D中，求兩點之間的最遠距離。

算法：随機選擇一行k，在這一行中找出最大的值作為直徑。

算法分析：該算法的近似比為2

D i j ≤ D i k + D k j ≤ D k l + D k l ≤ 2 D k l D_{ij} \leq D_{ik} +D_{kj} \leq D_{kl} +D_{kl} \leq 2D_{kl} Dij​≤Dik​+Dkj​≤Dkl​+Dkl​≤2Dkl​

排序連結清單搜尋的亞線性算法

定義：

排序雙向有序連結清單R，給定元素x，判斷x是否在R中。

這個R的資料結構，可以通過索引通路元素意味着可以随機抽取，并且每個元素都有指針可以通路相鄰的有序元素。

算法：

1随機在R中抽取 θ ( R ) \theta(\sqrt R) θ(R ​)個元素。構成集合S

2在S中找出p,q使得 p ≤ x ≤ p p \leq x \leq p p≤x≤p且在S中p,q間沒有其他元素。

3在p元素開始搜尋x，搜尋到傳回是。

算法分析：

時間複雜度為 O ( n ) O(\sqrt n) O(n ​),算法運作的時間為 O ( n ) O(\sqrt n) O(n ​)+(p,q間的元素個數)。S中的元素是随機選取，pq以|S|/n的機率選取且是相鄰的，是以在R中pq間元素個數的期望為n/|S|

多邊形交集問題

定義：判斷兩個簡單多邊形A,B是否相交

算法：

1 在A,B中等機率的選擇 θ ( n ) \theta (\sqrt n) θ(n ​)個頂點構成集合 C A , C B C_A,C_B CA​,CB​

2 在 O ( n ) O(\sqrt n) O(n ​)的時間内檢查 C A , C B C_A,C_B CA​,CB​是否相交，如果不相交則生成一條分隔 C A , C B C_A,C_B CA​,CB​的直線L

3 根據L判斷A,B是否相交

我們使用L來定義 P A , P B P_A,P_B PA​,PB​ a 是在L上A的點，a1,a2是a相鄰的兩個點如果這兩個點在于 C A C_A CA​在同側，則 P A P_A PA​為空。由于是簡單多邊形是以這兩個點隻有一個可能在 C A C_A CA​的另一側，我們這樣這個點的方向周遊知道點再次通過L，我們将周遊的點構成 P A P_A PA​。其大小為 O ( n ) O(\sqrt n) O(n ​)

是以A,B 相交可以轉化為A與PB相交或者B與PA相交，現在将說明輸入判斷B與PA相交，首先判定 C b 和 P A C_b和P_A Cb​和PA​是否相交，再按照一開始的方法确定分隔線Lb,通過Lb生成Qb，那麼B與PA相交等價于Qb與PA相交，而兩者的期望規模都是 O ( n ) O(\sqrt n) O(n ​)

是以我們可以在 O ( n ) O(\sqrt n) O(n ​)的時間内解決該問題。

連通分量個數估計

算法思想：

我們可以通過bfs精确的求出連同分量的個數，這樣每個點都要通路一次，時間複雜度為 O ( n d ) O(nd) O(nd)，d為節點的最大度數。

我們可以通過随機化的方法進行估算，節點u所在的連同分量的結點數即為 n u n_u nu​,那這個點的權重為 1 / n u 1/n_u 1/nu​。這樣精确的連同分量的個數是所有點的權重相加，但是我們考慮到如果 n u n_u nu​過大則對最後的貢獻很少，是以我們可以設定一個門檻值（ 2 / ϵ 2/\epsilon 2/ϵ)，當超過該值時我們停止bfs對該連同分量的搜尋。

算法：

随機取s（ θ ( 1 / ϵ 2 ) \theta(1/\epsilon^2) θ(1/ϵ2)）個點進行bfs的搜尋，根據門檻值與确定該點的權重，将這s個點的權重相加的到N，則連同分量的估計為 N n / s Nn/s Nn/s

算法分析

時間複雜度： O ( d ϵ 3 l o g ( 1 / ϵ ) ) O(\frac{d}{\epsilon^3}log(1/\epsilon)) O(ϵ3d​log(1/ϵ))

循環的輪數為 1 / ϵ 2 1/\epsilon^2 1/ϵ2,每一輪通路 2 / ϵ 2/\epsilon 2/ϵ個結點，在bfs的過程中代價為 d / ϵ d/\epsilon d/ϵ.因為在bfs的過程中需要确定點是否被通路是以要建立通路節點的平衡二叉樹這樣插入、通路的代價為 l o g ( 2 / ϵ ) log(2/\epsilon) log(2/ϵ),最終證明出時間複雜度。

品質分析

P r [ ∣ C ‘ − C ∣ > ϵ n ] ≤ 1 / 3 Pr[|C`-C|>\epsilon n]\leq1/3 Pr[∣C‘−C∣>ϵn]≤1/3