יעילות אלגוריתמית
הוצג| English | משמעות |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | יעילות אלגוריתמית |
| slow/sləʊ/ | איטי |
| steps/steps/ | שלבים |
| reasonable/ˈriːzənəbl/ | סביר |
| unreasonable/ʌnˈriːzənəbl/ | לא סביר |
| heuristic/hjuːˈrɪstɪk/ | הוריסטיקה |
נכון לא תמיד מספיק טוב
- שני אלגוריתמים יכולים להיות שניהם נכונים, אך אחד עשוי להיות הרבה טוב יותר לשימוש.
- יעילות אלגוריתמית משווה אלגוריתמים לפי המשאבים שהם משתמשים בהם — בעיקר זמן וזיכרון.
- אלגוריתם שנכון אך איטי יכול להיות חסר תועלת עבור קלט גדול.
- לכן אנחנו זקוקים לדרך להשוות את איך הם קיימים (מתרחבים).
יעילות אלגוריתמית משווה אלגוריתמים על ידי:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
יעילות עוסקת בזמן ובזיכרון ככל שהקלט גדל.
ספירת צעדים ככל ש-n גדל
- הערכו את מספר הצעדים שאלגוריתם לוקח כאשר גודל הקלט שלו $n$ גדל.
- חיפוש ליני לוקח כ-$n$ צעדים; חיפוש בינארי כ-$\log_2 n$; השוואת כל זוג כ-$n^2$.
- ככל ש$n$ מתגדל, ההבדלים הללו הופכים לעצומים.
- הצורה של הגידול חשובה הרבה יותר משעון ריצה.
כיצד זמן הרצה גדל עם גודל n
הזז n והשוו את העקומות: log נשאר כמעט שטוח, n עולה באופן רציף, n² מתפוצץ. זוהי הסיבה שאנו משווים אלגוריתמים לפי אופן ההתפשטות שלהם, ולא בשעון.
התאם כל אלגוריתם למספר המשלים המוערך עבור גודל קלט n.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
קצבי צמיחה אלו קובעים איזה אלגוריתם יעלה בקנה מידה.
איזה סוג צמיחה נחשב לבלתי סביר כאשר n הופך לגדול?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
צמיחה מעריכית הופכת במהירות לאיטית מדי.
כאשר תשובה מדויקת איטית מדי, ______ מוצא פתרון מספק מהר.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
הוריסטיקה מחליפה תשובה מושלמת בשביל מהירות.
סביר מול לא סביר
- אנחנו מבדילים בין זמן ריצה סביר לבין לא סביר.
- בקירוב, גידול כמו $n$ או $n^2$ הוא סביר; הכפלת מספר הצעדים בכל פריט נוסף (כמו $2^n$) היא לא סבירה.
- כאשר תשובה מדויקת איטית מדי, השתמשו בהוריסטיקה — פתרון טוב מספיק שנמצא במהירות.
- לא מושלם, אך שימושי כאשר מושלם בלתי אפשרי בזמן.
חיפוש בינארי של 1,000,000 פריטים מסודרים דורש עד כמה שלבים? (2^20 ≈ מיליון)
Difficulty 2/5 · 140 coins + a small bonus on first completion today
מכיוון ש-2^20 הוא מעט מעל מיליון, ~20 חלוקות מספיקות.
אלגוריתם נכון עשוי להיות איטי מדי לשימוש עם קלטים גדולים.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
חובה שיהיה לו גם סיום בזמן סביר.
איטי מדי לשימוש
- ולכן, חלק מאלגוריתמים תקניים איטיים מדי כדי לרוץ בפועל על קלט גדול.
- להיות תקני אינו מספיק — אלגוריתם חייב גם להסתיים בתוך זמן סביר.
מיליון פריטים. חיפוש ליניארי ב-1,000,000 פריטים מסודרים עשוי לקחת עד 1,000,000 צעדים. חיפוש בינארי לוקח מקסימום כ-20 צעדים, כי $2^{20}$ הוא מעט מעבר למיליון. ברשימות קטנות ההפרש קשה למדידה; במיליון פריטים, הבינארי הוא הבחירה היחידה הסבירה.
יעילות אלגוריתמית משווה בין אלגוריתמים לפי המשאבים כאשר גודל הקלט $n$ גדל: ליניארי $n$, בינארי $\log_2 n$, זוגות כולם $n^2$. גידול כמו $n$ או $n^2$ נחשב סביר; $2^n$ נחשב לא סביר (יש להשתמש בהוריסטיקה). אלגוריתם תקני שאיטי מדי על קלט גדול אינו מספק.