相關總結參見 /p/60ea83ea17cc
壹個隨機算法的最壞運行時間幾乎總是和非隨機化算法的最壞情形運行時間相同。重要的區別在於，好的隨機化算法沒有不好的輸入，而只有壞的隨機數（相對於特定的輸入）。
比如說：對於快速排序，方法A用第壹個元素作為樞紐元，方法B使用隨機選出的元素作為樞紐元。
通過隨機化算法，特定的輸入不再重要。重要的是隨機數，我們可以得到壹個期望的運行時間，此時我們是對所有可能的隨機數取平均而不是對所有可能的輸入求平均。
隨機數有許多已知的統計性質；偽隨機數滿足這些性質的大部分。
真正需要的是隨機數的序列。這些數應該獨立地出現。
線性同余數發生器
產生隨機數的最簡單的方法是線性同余數發生器，由Lehmer於1951年提出：
例如：M = 11，x0 = 1
A = 7： 7， 5， 2， 3， 10， 4， 6， 9， 8， 1， 7 ，5 ，2... （周期為10 = M-1）
A = 5： 5， 3， 4， 9， 1， 5， 3， 4...（周期為5 < M -1）
壹個有問題的隨機數發生器（返回(0,1)開區間值）：乘法溢出
工作在32位機器上的隨機數發生器
證明：為什麽δ(xi)或者是0，或者是1
為什麽僅當余項的值小於0時，δ(xi)=1
說明：因為這裏是對M取余，所以是M的倍數則自然消掉；並且δ(xi)兩項都是取整函數，因此肯定為整數，另外xi+1總是介於1~M-1之間，因此當余項小於0，則取1
隨機化的第壹個用途是以O(lgn)期望時間支持查找和插入的數據結構。
每個2^i 結點就有壹個指針指向下壹個2^i結點，總的指針個數僅僅是加倍，但現在在壹次查找中最多考察floor(lgn)個結點。因此總的時間消耗為O(lgn)。
本質上是二分查找：
放松上面數據結構的結構條件，就構成了跳躍表：
如果我們想查找19是否存在？如何查找呢？我們從頭結點開始，首先和9進行判斷，此時大於9，然後和21進行判斷，小於21，此時這個值肯定在9結點和21結點之間，此時，我們和17進行判斷，大於17，然後和21進行判斷，小於21，此時肯定在17結點和21結點之間，此時和19進行判斷，找到了。
1）實現
2）空間大小耗費
3）查找
1-2-3跳躍表的實現特點：
在同壹層級的鏈表（不超過3個結點）中找到首個大於item的結點，然後向下移壹層。
4）插入
必須保證當壹個高度為h的新結點加入進來時不會產生具有四個高度為h的結點的間隙。
插入采用2-3-4樹的自頂向下的方法（保證當前結點不是4-結點）：（參考 /p/8258ed821859 ）
設在第L層，並要降到下壹層。如果下壹層的間隙容量是3，則提高該間隙的中間項使其高度為L，從而形成兩個容量為1的間隙。由於這使得朝下刪除的道路上消除了容量為3的間隙，因此插入式安全的。
5）刪除
刪除采用2-3-4樹的自頂向下的方法（保證當前結點不是2-結點）：（參考 /p/8258ed821859 ）
確定壹個大數是否是素數的問題。
結點包括：
具有最低優先級的結點必然是根。樹是根據優先級的N!種可能的排列而不是根據項的N!中排列形成的。
1）插入
插入之後，通過左旋和右旋恢復堆序性質：
2）刪除
這個刪除方法也可以采用紅黑樹的刪除方法，將刪除歸結為葉子節點的刪除。（使用後繼，這樣可以節省很多旋轉）