标签：#隨機化算法

随机化算法

隨機化演算法（）是在邏輯或執行過程中使用隨機性的演算法。這類演算法通常使用均勻隨機位元作為輔助輸入，以引導演算法的行為，並期望在所有可能的隨機選擇之平均情況下取得良好效能。因此，隨機化演算法的執行時間、輸出結果，或兩者都可能是隨機變數。 隨機化演算法可依其對正確性與執行時間的保證分為不同類型。一類演算法會使用隨機輸入，並總是以正確答案終止，其執行時間可能根據隨機選擇而改變，這類演算法稱為拉斯維加斯演算法。另一類演算法通常具有固定或有界的…