تصادف و احتمال در الگوریتم

الگوریتم‌های تصادفی: Fisher-Yates shuffle، انتخاب kتایی تصادفی، Las Vegas در برابر Monte Carlo

تصادف به کمک الگوریتم می‌آید

گاهی تصادف، الگوریتم را ساده‌تر یا سریع‌تر می‌کند! دو خانواده:

نوعتضمینمثال
Las Vegasجواب همیشه درست، زمان تصادفیQuick Sort تصادفی
Monte Carloزمان قطعی، جواب احتمالاً درستآزمون اول بودن Miller-Rabin

۱. Fisher-Yates Shuffle

به‌هم‌ریختن «بیاس» آرایه — هر جایگشتی احتمال دقیقاً 1/n!:

for i from n-1 downto 1:
    j = random(0, i)      # فقط 0 تا i!
    swap(arr[i], arr[j])

خطای رایج: j از کل آرایه (0 تا n−1) انتخاب شود ← بیاس! (بعضی جایگشت‌ها محتمل‌تر)

۲. انتخاب kتایی تصادفی

«از n آیتم، k نمونه تصادفی» بدون دانستن n از قبل (جریان داده!): Reservoir Sampling:

نتیجه: هر kتایی با احتمال برابر — حتی بدون دانستن طول جریان!

۳. Quick Sort تصادفی

پیوت تصادفی ← بدترین حالت O(n²) عملاً حذف می‌شود (احتمالش 2^(-n) مانند!). میانگین تضمین‌شده O(n log n).

۴. Monte Carlo: تخمین π

نقاط تصادفی در مربع؛ نسبت نقاط داخل دایره = π/4 — شبیه‌سازی، پایه علم داده و فیزیک محاسباتی!

نکته: random پایتون شبه‌تصادفی است (seed قابل بازتولید) — برای تست عالی، برای رمزنگاری نه (secrets استفاده کنید)!

جمع‌بندی

این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.

ابزارهای مرتبط