Algorithmic efficiency · יעילות אלגוריתמית
What we'll do
- Two programs can both be correct but take very different time.
- This lesson is about efficiency: how the work grows as the input grows.
- Read and think about the ideas; then a few short tasks let you count the steps yourself.
מה נעשה
- שני תוכניות יכולות להיות נכונות אך לוקח להם זמן שונה מאוד.
- שיעור זה עוסק ביעילות: איך העבודה גדלה כשהקלט גדל.
- קרא וחשוב על הרעיונות; לאחר מכן כמה משימות קצרות מאפשרות לך ספור את השלבים בעצמך.
Counting the work
- We measure an algorithm by how many steps it does, not seconds.
- Steps in seconds depend on the computer; counting steps does not.
- More input usually means more steps. The question is how much more.
ספירת העבודה
- אנו מודדים אלגוריתם לפי כמה שלבים הוא מבצע, לא בשניות.
- שלבים בשניות תלויים במחשב; ספירת שלבים אינה תלויה בכך.
- קלט יותר בדרך כלל פירושו שלבים יותר. השאלה היא כמה יותר.
Reasonable vs unreasonable run time
- Some algorithms grow slowly: double the input, do about double the work.
- Some algorithms grow fast: a little more input means a huge jump in work.
- "Reasonable" run time grows slowly enough to finish; "unreasonable" blows up.
זמן הרצה סביר מול לא סביר
- חלק מהאלגוריתמים גדלים לאט: הכפלת הקלט, ביצוע כפול של העבודה.
- חלק מהאלגוריתמים גדלים מהר: מעט קלט נוסף פירושו קפיצה עצומה בעבודה.
- זמן הרצה "סביר" גדל לאט מספיק כדי להסתיים; "לא סביר" מתפוצץ.
Input size: 10 20 40
Search a list: 10 20 40 (slow growth - reasonable)
Try all orders: 3,628,800 ... a number with 48 digits (explodes!)
A tiny demo: counting steps
- Below we count the comparisons a linear search makes.
- The count grows in step with the list size — slow, steady growth.
- Try changing the size to see the count follow it.
דוגמה קטנה: ספירת צעדים
- למטה אנו סופרים את ההשוואות שעורך חיפוש ליניארי.
- הספירה עולה בהתאם לגודל הרשימה — גידול איטי ויציב.
- נסה לשנות את הגודל כדי לראות כיצד הספירה עוקבת אחריו.
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))
When fast is not enough
- Some problems have no known fast algorithm.
- The only methods try a huge number of possibilities — too slow for big input.
- For these, we often accept a good-enough answer instead of the perfect one.
כשמהירות אינה מספקת
- ישנם בעיות ללא אלגוריתם מהיר ידוע.
- השיטות היחידות מנסות מספר עצום של אפשרויות — איטיות מדי עבור כניסות גדולות.
- עבור בעיות אלו, לעיתים קרובות מקבלים פתרון מספק במקום המושלם.
Undecidable problems
- Worse than slow: some problems cannot be solved by any algorithm at all.
- These are called undecidable problems.
- No matter how fast computers get, no program can always give the right answer.
בעיות בלתי-ניתנות להכרעה
- גרוע יותר מאיטיות: ישנן בעότητες שאינן ניתנות לפתרון על ידי כל אלגוריתם כלל.
- נקראות לבעיות אלו בעיות בלתי-ניתנות להכרעה.
- לא משנה כמה המחשבים יהפכו מהירים יותר, אין תוכנית שתוכל תמיד לתת את התשובה הנכונה.
Fast : finishes quickly, even for big input
Slow but doable : finishes, but may take a very long time
Undecidable : no algorithm can solve it for every input
Key ideas to remember
- Efficiency is about how work grows with input size.
- Slow-growing algorithms scale to big inputs; fast-growing ones do not.
- Some problems are unreasonable to solve exactly, and some are undecidable.
רעיונות מפתח לזכירה
- יעילות עוסקת בכך שהעבודה עולה עם גודל הכניסה.
- אלגוריתמים עם גידול איטי מתאים לכניסות גדולות; אלגוריתמים עם גידול מהיר אינם מתאימים.
- ישנן בעיות שבלתי סביר לפתור במדויק, וישנן בעיות בלתי-ניתנות להכרעה.
Common mistakes
- Big-O describes how the running time GROWS with the input size.
- A reasonable-time algorithm scales; an unreasonable one does not.
טעויות נפוצות
- Big-O מתאר כיצד זמן הריצה עולה עם גודל הכניסה.
- אלגוריתם בעל זמן סביר מתאים; אלגוריתם בלתי-סביר אינו מתאים.
Now you try
- Write small functions that count steps to feel how the work grows.
- Compare a single loop, a nested loop, and "try all orders". Press Check answer.
כעת תנסו בעצמכם
- כתוב פונקציות קטנות שסופרות צעדים כדי להרגיש כיצד העבודה עולה.
- השווה לולאה אחת, לולאה מקוננת ו"נסה את כל ההתאמויות". לחץ על בדוק תשובה.
How algorithms scale · כיצד אלגוריתמים סוקליים
As input grows, O(n²) explodes while O(log n) barely moves. · ככל שהקלט גדל, O(n²) מתפוצץ בעוד ש-O(log n) כמעט לא זז.
Write scan_compares(data, target) that returns how many comparisons a linear search makes. Compare each item to target, counting one each time, and stop as soon as you find it. If it is not in the list, you compared every item. Example: scan_compares([5, 8, 2], 8) → 2. · כתוב scan_compares(data, target) שמחזיר כמה השוואות ביצוע חיפוש ליניארי. השווה כל פריט ל-target, סופר אחד בכל פעם, ו-עצור ברגע שמצאת אותו. אם הוא אינו ברשימה, השווית כל פריט. דוגמה: scan_compares([5, 8, 2], 8) → 2.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Write pair_count(n) that uses a loop inside a loop (both over range(n)) and returns how many times the inner step runs. This is n × n. Example: pair_count(3) → 9. This grows much faster than a single loop. · כתוב pair_count(n) שמשתמש במחזור בתוך מחזור (שניהם על range(n)) ומחזיר כמה הפעמים שלב הפנימי רץ. זהו n × n. דוגמה: pair_count(3) → 9. זה גדל הרבה יותר מהר ממחזור יחיד.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Write count_orderings(n) that returns how many different orders n items can be placed in — that is 1 × 2 × ... × n (n factorial). count_orderings(0) is 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million. · כתוב count_orderings(n) שמח多少 את מספר הסדרים השונים בהם ניתן לסדר n פריטים – כלומר 1 × 2 × ... × n (נכנס). count_orderings(0) הוא 1. דוגמה: count_orderings(3) → 6. שימו לב כמה זה מתפוצץ מהר: count_orderings(10) מעל 3 מיליון.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.