אלגוריתם אקראי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ תיקון קל. יש חפיפה עם מכונת טיורינג הסתברותית |
מאין תקציר עריכה |
||
שורה 7:
מקובל לחלק אלגוריתמים אקראיים לשתי משפחות עיקריות:
* '''[[אלגוריתמי לאס וגאס]]''' הינם אלגוריתמים אשר תמיד מוצאים תשובה נכונה לבעיה, ומשתמשים באקראיות רק על מנת לנסות ולשפר את זמן הריצה. דוגמה ידועה לאלגוריתם ממין זה הוא [[מיון|אלגוריתם המיון]] [[מיון מהיר]] (באנגלית: quicksort).
* '''[[שיטת מונטה קרלו|אלגוריתמי מונטה קרלו]]''' הינם אלגוריתמים אשר עלולים להחזיר תשובה לא נכונה לבעיה. דוגמה ידועה לאלגוריתם ממין זה הוא [[
ב[[מדעי המחשב]] מוגדרות מחלקות [[סיבוכיות]] המתאימות לבעיות אשר יש עבורן אלגוריתם אקראי [[חישוב יעיל|יעיל]]:
|