Monte Carlo vs Las Vegas

Monte Carlo 演算法

特性：執行時間固定，但結果可能錯誤（錯誤率可控）

用 Monte Carlo 估計圓周率

import random

def estimate_pi(n_points=100000):
    inside = 0
    for _ in range(n_points):
        x, y = random.random(), random.random()
        if x*x + y*y <= 1:
            inside += 1
    return 4 * inside / n_points

print(f"π ≈ {estimate_pi(1000000)}")  # ≈ 3.1416

Las Vegas 演算法

特性：結果永遠正確，但執行時間是隨機的

Las Vegas 隨機化快速排序

def randomized_quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return randomized_quicksort(left) + mid + randomized_quicksort(right)

Vibe Prompt

🔥 詠唱：「比較固定 pivot 與隨機 pivot 的快速排序在不同輸入下的效能，畫出執行時間分布圖。」

深入理解：兩類隨機化演算法的核心差異

| 特性 | Monte Carlo | Las Vegas | |------|:-----------:|:---------:| | 結果正確性 | 可能錯誤（機率可控） | 永遠正確 | | 執行時間 | 固定（O(n)） | 隨機（期望 O(n)，可能 O(∞)） | | 錯誤處理 | 允許錯誤率 ε | 不允許錯誤 | | 典型例子 | 圓周率估計、質數測試 | 隨機化快速排序、隨機化選擇 | | 信心提升 | 增加樣本數 | 多次執行取最快 |

如何選擇？

如果結果可以容忍小錯誤（如估計、模擬）→ Monte Carlo
如果結果必須完全正確（如排序、選擇）→ Las Vegas
如果執行時間必須固定（如即時系統）→ Monte Carlo
如果避免最壞情況（如排序演算法）→ Las Vegas

錯誤率與信心

Monte Carlo 的誤差隨樣本數增加而減少： $$\text{Error} \propto \frac{1}{\sqrt{n}}$$

要讓誤差減半，需要 4 倍的樣本數！

關鍵要點

✅ Monte Carlo：固定時間，可能錯誤（錯誤率可控）
✅ Las Vegas：結果正確，時間隨機（期望時間可控）
✅ 隨機化 pivot 避免 Quicksort 的 O(n²) 最壞情況
✅ 隨機化不保證「更快」，但保證「不會總是很慢」
✅ 隨機化是打破對手惡意輸入的重要工具

測試驗證：確保功能正確運作
最佳化：調整效能與使用者體驗

常見錯誤

程式碼範例

Monte Carlo vs Las Vegas：怎麼選？

這兩個名字來自賭城，但它們解決的是完全不同的問題：

| 特性 | Monte Carlo | Las Vegas | |:----|:----------|:---------| | 答案正確性 | 可能錯（以機率為代價） | 保證正確 | | 執行時間 | 固定（已知時間內完成） | 不固定（可能很慢或無窮） | | 典型應用 | 數值積分、物理模擬、機器學習 | 快速排序、隨機化演算法 | | 失敗模式 | 給出錯誤答案 | 不給答案（太久） |

在真實專案中如何選擇？

需要即時回應（例如遊戲 AI、即時圖形渲染）→ Monte Carlo，因為時間可控
答案必須正確（例如醫療診斷、航太計算）→ Las Vegas，因為保證正確
大數據近似（例如統計分析、機率估計）→ Monte Carlo
演算法加速（例如 QuickSort 隨機化 pivot）→ Las Vegas

事實上，很多系統同時使用兩者。Google 的搜尋結果排序使用 Monte Carlo 模擬使用者的點擊行為來估計相關性分數，而後端的文件檢索則使用 Las Vegas 類型的隨機化演算法來確保找到所有相關文件。

下一章預告：隨機化快速排序

這章建立了隨機化演算法的兩種分類。下一章我們將深入 Las Vegas 類型的代表——隨機化快速排序，看隨機選 pivot 如何在平均情況下達到 O(n log n) 的效能，同時避免 Worst Case O(n²)。