יסודות מדעי המחשב — מרחב למידה אישי

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

יסודות ניתוח יעילות אלגוריתמים

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

מורכבות זמן (Time Complexity): מדד לכמות הזמן שהאלגוריתם צורך כפונקציה של גודל הקלט (n).

מורכבות מקום (Space Complexity): מדד לכמות הזיכרון שהאלגוריתם צורך כפונקציה של גודל הקלט (n).

סימון אסימפטוטי (Asymptotic Notation)

כדי לתאר את קצב הגידול של פונקציית הזמן/מקום של אלגוריתם, אנו משתמשים בסימונים אסימפטוטיים המתעלמים מקבועים ומאיברים מסדר נמוך. הסימון הנפוץ ביותר הוא Big O.

סימון Big O (O-notation): חסם עליון (Upper Bound) אסימפטוטי. מתאר את המקרה הגרוע ביותר של האלגוריתם, או את קצב הגידול המקסימלי שלו. לדוגמה, O(n) פירושו שהזמן או המקום יגדלו באופן ליניארי עם גודל הקלט.

Big O (O)

חסם עליון: מתאר את קצב הגידול המקסימלי של האלגוריתם (המקרה הגרוע ביותר). שימושי להבטחת ביצועים.

Big Omega (Ω)

חסם תחתון: מתאר את קצב הגידול המינימלי של האלגוריתם (המקרה הטוב ביותר). שימושי להבנת גבולות תחתונים.

Big Theta (Θ)

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

ניתוח מורכבות בקוד פייתון

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

דוגמאות למורכבות נפוצות

O(1) - קבוע: גישה לאיבר במערך לפי אינדקס, פעולות אריתמטיות בסיסיות.
O(log n) - לוגריתמי: חיפוש בינארי במערך ממויין.
O(n) - ליניארי: מעבר על כל איברי רשימה (לולאה בודדת), חיפוש ליניארי.
O(n log n) - ליניארי-לוגריתמי: אלגוריתמי מיון יעילים כמו Merge Sort או Quick Sort.
O(n²) - ריבועי: לולאות מקוננות (nested loops) העוברות על כל זוגות האיברים, כמו במיון בועות (Bubble Sort) או כפל מטריצות פשוט.
O(2ⁿ) - אקספוננציאלי: פתרון בעיות ברוט-פורס (Brute-Force) מסוימות, כמו בעיית הסוכן הנוסע (TSP) בדרך נאיבית.

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

הערכת ביצועים ופתרון בעיות נפוצות

הבנת מורכבות מאפשרת לנו לבחור את האלגוריתם המתאים ביותר לבעיה נתונה ולשפר את ביצועי הקוד.

מקרים שונים: הטוב, הממוצע והגרוע

המקרה הגרוע (Worst Case): המקרה שבו האלגוריתם מבצע את המספר המרבי של פעולות. זהו המדד הנפוץ ביותר לניתוח יעילות.
המקרה הטוב (Best Case): המקרה שבו האלגוריתם מבצע את המספר המינימלי של פעולות. פחות רלוונטי בדרך כלל.
המקרה הממוצע (Average Case): ממוצע של מספר הפעולות על פני כל הקלטים האפשריים, בהנחה של התפלגות מסוימת. קשה יותר לחישוב.

מורכבות מקום (Space Complexity)

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

שאלות לדיון

נתחו את מורכבות הזמן והמקום של הפונקציה הבאה:


def find_max(arr):
    max_val = arr[0]
    for x in arr:
        if x > max_val:
            max_val = x
    return max_val

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

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

לגבי find_max: מורכבות זמן היא O(n) מכיוון שהלולאה עוברת על כל n האיברים ברשימה פעם אחת. מורכבות מקום היא O(1) מכיוון שהיא משתמשת במספר קבוע של משתנים ללא תלות בגודל הקלט.
השוואת חיפוש: חיפוש ליניארי הוא O(n), חיפוש בינארי הוא O(log n). חיפוש בינארי עדיף בהרבה עבור רשימות גדולות וממוינות. חיפוש ליניארי מתאים לרשימות קטנות או לא ממוינות, או כאשר אין אפשרות למיין.
חשיבות מורכבות מקום: זיכרון הוא משאב מוגבל. אלגוריתם עם מורכבות מקום גבוהה (לדוגמה, O(n^2) או O(2^n) עבור נתונים גדולים) עלול לגרום לקריסת התוכנית (MemoryError) או להאט אותה משמעותית עקב שימוש בזיכרון וירטואלי. דוגמה: שמירת מטריצת שכנויות מלאה עבור גרף דליל מאוד.
השפעת מבני נתונים: שימוש במילון (hash map) מאפשר גישה, הכנסה ומחיקה ב-O(1) בממוצע, לעומת O(n) ברשימה. לדוגמה, בדיקת קיום איבר ברשימה היא O(n), בעוד שבמילון היא O(1) בממוצע. זה יכול להפוך אלגוריתם מ-O(n^2) ל-O(n) במקרים מסוימים.

מצאתם טעות או שחסר משהו?