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 的快速排序在不同輸入下的效能，畫出執行時間分布圖。」