主方法

主定理

設 $a >= 1$ 和 $b > 1$ 為常數，設 $f(n)$ 為一函式，$T(n)$ 由遞迴式 $$T(n) = aT(\frac b n) + f(n)$$ 對非負整數定義。其中 $n/b$ 指 $\lfloor n/b \rfloor$ 或 $ \lceil n/b \rceil $。那麼 $T(n)$ 可能有如下的漸近界：

1. 若對於某常數 $\epsilon > 0$，有 $ f(n) = O(n^{\log_b a} - \epsilon)$，則 $ T(n) = \Theta(n^{\log_b a})$；

2. 若 $f(n) = \Theta(n^{\log_b a})$，則 $T(n) = \Theta(n^{\log_b a} \lg n)$ ；

3. 若對某常數 $\epsilon > 0$，有 $f(n) = \Omega(n^{\log_b a} + \epsilon)$ ，且對常數 $c > 1$ 與所有足夠大的 $n$ ，有 $af(n/b) <= cf(n)$ ，則 $T(n) = \Theta(f(n))$ 。

直覺理解

哪個大就決定於哪個。

機率分析和隨機演算法

指示器隨機變數

感覺講的很厲害，但是實際上好像是比較簡單的概統思想。只是將一個事件期望解釋成完備事件組的期望的和。應該像是全機率公式的推廣吧。

隨機演算法

• 機率分析 如果我們說一個輸入的分佈是確定的，比如是完全隨機的，這樣我們會分析演算法得到一個期望。這個時候，我們分析的演算法本身是確定的。 對任何的確定的輸入，給出的結果是確定的。

• 隨機演算法 我們在演算法內部加入隨機性。比如在輸入之後對輸入進行隨機排序。 這樣，對任何的確定的輸入，給出的結果也是不定的的。

  • 隨機化演算法

    1. PERMUTE-BY-SORTING 對每個元素給定隨機的優先順序，按照優先順序進行排序。

    2. RANDOMIZE-IN-PLACE 從第一個元素開始依次和之後的元素進行隨機交換。