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