ランダム化Quickselect

🔥 Vibe プロンプト

「1000万個の数値の中央値をQuickselectで検索。期待時間と最悪時間を表示。」

import random

def quickselect(arr, k):
    if len(arr) == 1:
        return arr[0]
    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]
    if k < len(left):
        return quickselect(left, k)
    elif k < len(left) + len(mid):
        return mid[0]
    else:
        return quickselect(right, k - len(left) - len(mid))

import time
data = [random.randint(0, 1000000) for _ in range(100000)]
start = time.time()
med = quickselect(data, len(data)//2)
print(f"中央値: {med}, 時間: {(time.time()-start)*1000:.2f}ms")
print("ランダム化でO(n²)の最悪ケースを回避！")

なぜランダム化？

| 手法 | 平均 | 最悪 | |------|------|------| | 決定論的 | O(n) | O(n²) | | ランダム化 | O(n) | O(n) (確率的) |

応用

• リアルタイム中央値計算
• データベース順序統計
• 負荷分散
• 外れ値検出

重要なポイント

• コアコンセプトをしっかり理解する
• ハンズオンコード例で実践する
• 実世界の問題に応用する
• 演習で知識を強化する

さらに学ぶ

• 公式ドキュメント
• GitHubのオープンソースプロジェクト
• コミュニティフォーラムとディスカッション
• 関連コースとチュートリアル