אלגוריתם אקראי – הבדלי גרסאות

 

באופן פורמלי, מוגדר אלגוריתם אקראי כ[[מכונת טיורינג]] אשר בנוסף לסרטים הרגילים שלה יש לה גישה לסרט קלט נוסף אשר מכיל רצף של "0"-ים ו-"1"-ים, המייצגים סדרה של הטלות אקראיות [[מאורעות בלתי תלויים|בלתי תלויות]] של מטבעות. ניתן להגדיר פלט של מכונת טיורינג כנ"ל כ[[התפלגות]] על פלטי המכונה בהינתן [[התפלגות אחידה]] בלתי תלויה של איברי סדרת הסרט הנוסף. פורמלית, [[זמן ריצה|זמן הריצה]] של אלגוריתם אקראי הינו [[משתנה מקרי]], ולרוב נמדדת יעילות האלגוריתם על פי [[תוחלת]] זמן הריצה שלו.