از ویکی‌پدیا، دانشنامهٔ آزاد.

الگوریتم تصادفی الگوریتمی است که اجازه‌ٔ گرداندن یک سکهٔ سالم را دارد! بدین معنی که ماشین پیاده کننده این الگوریتم به تولید کنندهٔ اعداد شبه تصادفی (pseudo-random number generator) دسترسی دارد. این الگوریتم نوعاً با هدف بالا بردن کارایی در حالت‌های معمول از یک ورودی دودویی کمکی برای رفتارهای خود استفاده می‌کند. کارایی الگوریتم با یک متغیر تصادفی که به بیت‌های تصادفی داده شده بستگی دارد، تغییر می‌‌یابد که (امیدوارانه) امید ریاضی خوبی را شامل می‌شود. احتمال وقوع بدترین حالت آنقدر کم است که می‌توان از آن صرفنظر کرد.

به عنوان یک مثال جالب فرض کنید می‌خواهیم حرف «الف» را از میان آرایهٔ n خانه‌ای پیدا کنیم در حالی که می‌دانیم نصف خانه‌ها «ب» و نصف دیگر «الف» است. یک روش مشخص نگاه کردن به تمام خانه‌های آرایه است که اگر «ب»ها اول باشند n/۲ حالت را باید برای پیدا کردن «الف» بررسی کنیم. در حقیقت با هر استراتژی جستجویی این احتمال ثابت است ولی اگر ما خانه‌های آرایه را تصادفی می‌آزمودیم‌، آنگاه می‌توانستیم با هر ورودی سزیعا یک حرف «الف» را با احتمال بالایی پیدا کنیم.

الگوریتم‌های تصادفی بویژه در مواردی استفاده دارند که با یک دشمن یا مهاجم بد خواهی! مواجهیم که از روی عناد ورودی بدی را برای ما فراهم می‌کند(آنالیز رقابتی). به همین دلیل انتخاب تصادفی پایه رمزنگاری را تشکیل می‌‌دهد.

در مثال بالا الگوریتم تصادفی همیشه درست جواب می‌‌دهد تنها احتمال کوچکی وجود دارد که زمان زیادی برای رسیدن به پاسخ صرف کند. در بعضی مواقع ما از الگوریتم با اجازه دادن ایجاد احتمال کمی خطا انتظار سرعت بالاتر را داریم. الگوریتمهای از نوع اول را لاس وگاس (Las Vegas algorithms) و نوع اخیر را مونت کارلو (Monte Carlo algorithms) می‌‌نامند. مشاهده می‌کنیم که هر الگوریتم لاس وگاس را با گرفتن جوابی احتمالا نادرست در زمانی مشخص و محدود شده به الگوریتم مونت کارلو تبدیل می‌شود. Quicksort معروفترین الگوریتم تصادفی کاربردی در جهان حقیقی است.

فرستنده : نسیم