יחידה 12: עקרונות אלגוריתמיים וביצועים

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

מהי יעילות אלגוריתמית ולמה היא חשובה?

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

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

סיבוכיות זמן ומקום: הכלים לניתוח

כדי לכמת את יעילות האלגוריתם, אנו משתמשים בשני מדדים עיקריים:

הכלי הסטנדרטי לתיאור סיבוכיות הוא

קטגוריות סיבוכיות נפוצות וניתוח קוד

הכרת קטגוריות הסיבוכיות הנפוצות חיונית להערכה מהירה של אלגוריתמים:

קטגוריות נוספות שחשוב להכיר: O(n^2) - ריבועי (לולאות מקוננות), O(2^n) - מעריכי (בעיות חיפוש בכוח גס), O(n!) - פקטוריאלי (בעיות קומבינטוריות).

כיצד מנתחים סיבוכיות של קוד פייתון?

• פעולות בסיסיות: השמה, פעולות אריתמטיות, גישה לאיבר ברשימה/מילון לפי אינדקס/מפתח – לרוב O(1).
• לולאות (for/while): אם לולאה רצה n פעמים וכל פעולה בתוכה היא O(1), הסיבוכיות הכוללת היא O(n).
• לולאות מקוננות: אם לולאה חיצונית רצה n פעמים ולולאה פנימית רצה m פעמים, הסיבוכיות היא O(n*m). אם שתיהן תלויות באותו n, הסיבוכיות היא O(n^2).
• קריאות לפונקציות: יש לכלול את סיבוכיות הפונקציה הנקראת.
• מבני נתונים: יש להכיר את סיבוכיות הפעולות הבסיסיות על רשימות (list), מילונים (dict) וקבוצות (set) בפייתון. לדוגמה, חיפוש ברשימה הוא O(n), בעוד חיפוש במילון הוא O(1) בממוצע.

שיקולים מעשיים ונקודות מבחן

בבחירת אלגוריתם, לעיתים קרובות ישנו

שאלות לדיון

• הסבירו מדוע אלגוריתם עם סיבוכיות זמן O(n^2) עשוי להיות בלתי ישים עבור קלטים גדולים (לדוגמה, n=1,000,000), בעוד אלגוריתם O(n log n) יהיה יעיל.
• תנו דוגמה לפעולה בפייתון שיש לה סיבוכיות זמן O(1) על רשימה, ודוגמה לפעולה שיש לה סיבוכיות זמן O(n) על רשימה. נמקו.
• כיצד סיבוכיות מקום יכולה להשפיע על בחירת אלגוריתם, גם אם סיבוכיות הזמן שלו נראית טובה מאוד? תנו דוגמה.
• נתחו את סיבוכיות הזמן של קטע הקוד הבא:

  def process_data(data):
      n = len(data)
      count = 0
      for i in range(n):
          for j in range(i, n):
              if data[i] == data[j]:
                  count += 1
      return count
  

נקודות לתשובת מודל

• O(n^2) מול O(n log n): יש להסביר את קצב הגידול השונה. עבור n=1,000,000, n^2 הוא 10^12 פעולות, בעוד n log n הוא כ-20*10^6 פעולות. ההבדל הוא עצום והופך את O(n^2) לבלתי מעשי.
• דוגמאות לפעולות על רשימה:
  • O(1): גישה לאיבר לפי אינדקס (לדוגמה, my_list[5]), הוספה בסוף (my_list.append(item) - אמורטי).
  • O(n): חיפוש איבר (item in my_list), הוספה בתחילת הרשימה (my_list.insert(0, item)), מחיקת איבר לפי ערך (my_list.remove(item)).
  הנימוק מתבסס על הצורך לעבור על חלק או כל איברי הרשימה.
• השפעת סיבוכיות מקום: אלגוריתם עם סיבוכיות זמן טובה אך סיבוכיות מקום גבוהה (לדוגמה, O(n) או O(n^2) מקום) עלול לגרום לחריגה מזיכרון (MemoryError) עבור קלטים גדולים, או להאט את המערכת עקב שימוש מוגבר בזיכרון ודפדוף (swapping) לדיסק. דוגמה: אלגוריתם מיון שדורש יצירת עותק שלם של הרשימה המקורית.
• ניתוח קטע הקוד:
  • הלולאה החיצונית רצה n פעמים (range(n)).
  • הלולאה הפנימית רצה מ-i עד n-1. במקרה הגרוע ביותר (כאשר i=0), היא רצה n פעמים. בממוצע, היא רצה כ-n/2 פעמים.
  • פעולת ההשוואה (data[i] == data[j]) וההוספה (count += 1) הן O(1).
  • מכיוון שיש לולאה מקוננת שכל אחת מהן תלויה ב-n, הסיבוכיות הכוללת היא O(n * n) = O(n^2).