拉斯維加斯演算法（Las Vegas algorithm）

想像一個魔術，結尾總是把對的牌翻到最上面，但每次表演要洗的次數都不同——有時很快，有時要擺弄好一陣子。拉斯維加斯演算法就像這樣：它一路上擲硬幣，給出的答案永遠正確，但跑多久要看運氣。你可以完全信任它的輸出，只是無法保證它何時結束。

精確地說：拉斯維加斯演算法使用隨機性，而且永遠回傳正確的結果（或誠實地回報失敗並重試），但它的執行時間是一個隨機變數。我們通常以期望執行時間來概括它——也就是對每個固定輸入，針對演算法自己擲的硬幣取平均。隨機快速排序是經典例子：它每次挑一個隨機樞紐，排序永遠正確，期望時間為 O(n log n)，雖然一連串倒楣的樞紐選擇仍可能花 O(n^2)。一個簡單的模板是「生成並測試」：不斷做隨機猜測並檢查，回傳第一個通過的猜測——例如不斷抽取隨機元素，直到抽到一個不是重複的為止。

當錯誤答案不可接受、但等待時間可變動沒關係時，拉斯維加斯就是對的模型——排序、搜尋、建立資料結構。你接受的代價是時間的不確定，而非正確性的不確定。誠實的提醒：期望時間是對硬幣取的平均，不是最壞情況的保證，因此單次執行仍可能很慢；而且分析假設有一個真正隨機的位元來源，現實的偽隨機產生器只是近似它。