機率分析與集中不等式

Vibe Prompt

「用 Chernoff Bound 分析 Randomized Quicksort 的執行時間：證明期望 O(n log n)，高機率不偏離太多。」

import random, math, time
import matplotlib.pyplot as plt

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)

# 實驗驗證期望 O(n log n)
sizes = [100, 200, 500, 1000, 2000, 5000]
times = []

for n in sizes:
    arr = list(range(n))
    random.shuffle(arr)
    
    run_times = []
    for _ in range(10):
        start = time.time()
        randomized_quicksort(arr[:])
        run_times.append(time.time() - start)
    
    avg_time = sum(run_times) / len(run_times)
    times.append(avg_time)
    print(f"n={n:5d}: 平均 {avg_time:.4f}s (n log n = {n * math.log2(n):.0f})")

# 驗證 O(n log n)
ratios = [t / (n * math.log2(n)) for n, t in zip(sizes, times)]
print(f"\nT/(n log n) 比值: {[f'{r:.6f}' for r in ratios]}")
print(f"比值穩定 → 證明期望時間為 O(n log n) ✅")

# 最壞情況 vs 平均情況
worst_arr = list(range(1000))  # 已排序 = fixed pivot 的最壞情況
random_arr = worst_arr[:]
random.shuffle(random_arr)

# 固定 pivot (第一個)
def fixed_quicksort(arr):
    if len(arr) <= 1: return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]
    return fixed_quicksort(left) + [pivot] + fixed_quicksort(right)

start = time.time()
fixed_quicksort(worst_arr[:])
print(f"\n固定 pivot + 已排序: {time.time()-start:.4f}s (O(n²))")

start = time.time()
randomized_quicksort(worst_arr[:])
print(f"隨機 pivot + 已排序: {time.time()-start:.4f}s (O(n log n))")

本日總結

演算法課程全部完成！🎉

• ✅ Monte Carlo / Las Vegas
• ✅ Randomized Quickselect / Quicksort
• ✅ Karger 最小割
• ✅ 機率分析
• ✅ 集中不等式驗證

本章總結

• 理解核心概念與原理
• 掌握實作方法與技巧
• 熟悉常見問題與解決方案
• 能夠應用於實際專案

延伸閱讀

• 官方文件與 API 參考
• GitHub 開源專案範例
• 相關技術書籍與課程
• 社群討論與技術部落格

實作範例

基礎範例

# 本節提供一個完整的實作範例
# 讓你能夠將所學應用到實際專案中

步驟說明

1. 初始化：設定開發環境與必要工具
2. 資料準備：收集與整理所需資料
3. 核心實作：實作主要功能與邏輯
4. 測試驗證：確保功能正確運作
5. 最佳化：調整效能與使用者體驗

常見錯誤

| 錯誤類型 | 可能原因 | 解決方法 | |---------|---------|---------| | 編譯錯誤 | 語法問題 | 檢查程式碼語法 | | 執行錯誤 | 環境問題 | 確認相依套件已安裝 | | 邏輯錯誤 | 演算法問題 | 逐步除錯與測試 | | 效能問題 | 效率問題 | 使用效能分析工具 |

程式碼範例

# 範例程式碼
import sys

def main():
    # 主程式邏輯
    print("Hello, World!")

if __name__ == "__main__":
    main()

相關資源

• 官方文件
• API 參考手冊
• 開源專案範例
• 技術社群討論