יעילות אלגוריתמית
מה נעשה
- שני תוכניות יכולות להיות נכונות אך לוקח להם זמן שונה מאוד.
- שיעור זה עוסק ביעילות: איך העבודה גדלה כשהקלט גדל.
- קרא וחשוב על הרעיונות; לאחר מכן כמה משימות קצרות מאפשרות לך ספור את השלבים בעצמך.
ספירת העבודה
- אנו מודדים אלגוריתם לפי כמה שלבים הוא מבצע, לא בשניות.
- שלבים בשניות תלויים במחשב; ספירת שלבים אינה תלויה בכך.
- קלט יותר בדרך כלל פירושו שלבים יותר. השאלה היא כמה יותר.
זמן הרצה סביר מול לא סביר
- זמן סביר פירושו שמספר השלבים גדל כפולינומיה, או לאט יותר: קבוע, ליניארי, ריבועי או קובי.
- לולאה אחת היא ליניארית. לולאה בתוך לולאה היא ריבועית (n × n). ריבוע גדל מהר יותר מקוונית, והוא עדיין זמן סביר.
- זמן בלתי סביר פירונו גידול אקספוננציאלי או פיבונצ'יאלי. מעט יותר נתונים גורמים לעבודה להתפוצץ.
Input size: 10 20 40
Search a list: 10 20 40 (linear - reasonable)
Nested loops: 100 400 1,600 (square - still reasonable)
Try all orders: 3,628,800 ... 48 digits (factorial - unreasonable)
דוגמה קטנה: ספירת צעדים
- למטה אנו סופרים את ההשוואות שעורך חיפוש ליניארי.
- הספירה עולה בהתאם לגודל הרשימה — גידול איטי ויציב.
- נסה לשנות את הגודל כדי לראות כיצד הספירה עוקבת אחריו.
def count_steps(n):
steps = 0
data = list(range(n))
target = -1 # not in the list, so we scan everything
for item in data:
steps = steps + 1
if item == target:
break
return steps
print(count_steps(10))
print(count_steps(20))
print(count_steps(40))
כשמהירות אינה מספקת
- ישנם בעיות שאין להן אלגוריתם ידוע בזמן סביר.
- שיטה מדויקת עשויה לנסות כל תורמות. זהו גידול פיבונצ'יאלי, ולכן הוא בלתי סביר עבור כניסה גדולה.
- היוריסטיקה היא קיצור דרך שיכול לתת תשובה מספקת. אינה מובטחת להיות הטובה ביותר. אין צורך לזכור היוריסטיקה ספציפית אחת.
בעיות בלתי-ניתנות להכרעה
- גרוע יותר מאיטיות: ישנן בעότητες שאינן ניתנות לפתרון על ידי כל אלגוריתם כלל.
- נקראות לבעיות אלו בעיות בלתי-ניתנות להכרעה.
- לא משנה כמה המחשבים יהפכו מהירים יותר, אין תוכנית שתוכל תמיד לתת את התשובה הנכונה.
Reasonable : constant, linear, square or cube growth
Unreasonable : exponential or factorial growth
Undecidable : no algorithm can solve it for every input
רעיונות מפתח לזכירה
- יעילות עוסקת בכיצד מספר השלבים גודל עם גודל הכניסה, ולא כמה שניות מחשב אחד לוקח.
- גידול פולינומי או נמוך יותר הוא זמן סביר. לולאה מקושרת (n × n) עדיין נחשבת לסבירה.
- גידול אקספוננציאלי או פיבונצ'יאלי הוא בלתי סביר. ישנן בעיות שאף אינן חלטופיות.
טעויות נפוצות
- מכיוון שלולאה מקושרת נחשבת לבלתי סבירה. גידול ריבעי ומעוקב עדיין נחשב לזמן סביר.
- השימוש בסימון Big-O פורמלי כחוק מבחן. Big-O אינו נבחן. השורה היא פולינומית או נמוכה יותר, לעומת מעריכית או פקטוריאלית.
כעת תנסו בעצמכם
- כתוב פונקציות קטנות שסופרות צעדים כדי להרגיש כיצד העבודה עולה.
- השוו לולאה אחת, לולאה מקושרת ו"ניסוי כל התורמות". הלולאה המקושרת עדיין נחשבת לזמן סביר. לחץ על בדוק תשובה.
כיצד אלגוריתמים סוקליים
גודל ריבעי עולה מהר יותר מקו ישר, ועדיין סביר בזמנית. גודל פקטוריאל הוא בלתי סביר.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב scan_compares(data, target) שמחזיר כמה השוואות ביצוע חיפוש ליניארי. השווה כל פריט ל-target, סופר אחד בכל פעם, ו-עצור ברגע שמצאת אותו. אם הוא אינו ברשימה, השווית כל פריט. דוגמה: scan_compares([5, 8, 2], 8) → 2.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב pair_count(n) שמשתמש במחזור בתוך מחזור (שניהם על range(n)) ומחזיר כמה הפעמים שלב הפנימי רץ. זהו n × n. דוגמה: pair_count(3) → 9. זה גדל הרבה יותר מהר ממחזור יחיד.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב count_orderings(n) שמחזיר כמה סדרות שונות n פריטים יכולים להיות מסודרים בן — כלומר 1 × 2 × ... × n (פקטוריאל של n). count_orderings(0) הוא 1. דוגמה: count_orderings(3) → 6. שימו לב כמה זה מתפוצץ: count_orderings(10) הוא מעל 3 מיליון.
לחץ על הרץ כדי לראות את התוצא כאן.