כל מה שרצית לדעת על אלגוריתם אקראי:
אלגוריתם אקראי (באנגלית: randomized algorithm) או אלגוריתם הסתברותי הוא אלגוריתם המשתמש באקראיות במהלך ריצתו, או – במלים אחרות – רשאי "להטיל מטבעות אקראיים" כחלק מפעולתו.
באופן פורמלי, מוגדר אלגוריתם אקראי בעזרת מכונת טיורינג הסתברותית: מכונת טיורינג רגילה אשר בנוסף לסרטים הרגילים שלה יש לה גישה לסרט קלט נוסף אשר מכיל רצף של "0"-ים ו-"1"-ים, המייצגים סדרה של הטלות אקראיות בלתי תלויות של מטבעות.
ניתן להגדיר פלט של מכונת טיורינג כנ"ל כהתפלגות על פלטי המכונה בהינתן התפלגות אחידה בלתי תלויה של איברי סדרת הסרט הנוסף.
פורמלית, זמן הריצה של אלגוריתם אקראי הינו משתנה מקרי, ולעתים נמדדת יעילות האלגוריתם על פי תוחלת זמן הריצה שלו.