פרק 16 - מבוא ליעילות וסיבוכיות זמן ריצה

⏱ 14 דקות קריאה

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

1. למה לא פשוט למדוד בשעון עצר?

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

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

2. גודל הקלט וסימון Big-O

את גודל הקלט מסמנים בדרך כלל באות n - למשל, מספר האיברים במערך. כדי לתאר איך מספר הפעולות גדל ביחס ל-n, משתמשים בסימון Big-O: תיאור קצר של קצב הגידול, תוך התעלמות מקבועים ומפרטים קטנים שלא משפיעים כשה-n גדול מאוד.

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

3. סיבוכיות קבועה - O(1)

כשמספר הפעולות לא תלוי בכלל בגודל הקלט, אומרים שהסיבוכיות קבועה - O(1). גישה ישירה לתא במערך היא הדוגמה הקלאסית: לא משנה אם למערך יש 10 איברים או מיליון, הגישה ל-arr[0] לוקחת אותו מספר פעולות.

Java


static int firstElement(int[] arr) {
    return arr[0];
}

בלי קשר לגודל arr, הפונקציה מבצעת בדיוק פעולה אחת - גישה לאינדקס 0. זו סיבוכיות O(1).

4. סיבוכיות ליניארית - O(n)

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

Java


static int sumArray(int[] arr) {
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
    }
    return sum;
}

הלולאה רצה n פעמים (פעם אחת לכל איבר במערך), וכל סיבוב מבצע מספר קבוע של פעולות (חיבור אחד). לכן הסיבוכיות היא O(n) - אם מכפילים את גודל המערך, מכפילים גם את מספר הפעולות.

5. סיבוכיות ריבועית - O(n^2)

כשלולאה נמצאת בתוך לולאה אחרת, וכל אחת רצה עד n, מספר הפעולות גדל לפי n בריבוע - סיבוכיות ריבועית, O(n^2).

Java


static int countPairs(int[] arr) {
    int count = 0;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            count++;
        }
    }
    return count;
}

עבור כל אחת מ-n האיטרציות של הלולאה החיצונית, הלולאה הפנימית רצה שוב n פעמים - סך הכול n * n = n^2 פעולות. אם n מוכפל, מספר הפעולות לא מוכפל - הוא מוכפל פי ארבע.

6. למה זה בכלל משנה? השוואת קצב גידול

ההבדל בין O(n) ל-O(n^2) נראה קטן על קלט קטן, אבל מתפוצץ על קלט גדול:

n = 10: לולאה בודדת מבצעת כ-10 פעולות, לולאה מקוננת מבצעת כ-100.

n = 1,000: לולאה בודדת מבצעת כ-1,000 פעולות, לולאה מקוננת מבצעת כ-1,000,000.

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

7. טעויות נפוצות

לולאה שרצה מספר קבוע של פעמים היא לא O(n): לולאה שתמיד רצה 10 פעמים, לא משנה מה גודל הקלט, היא O(1) - כי מספר הפעולות שלה לא תלוי ב-n.

שתי לולאות ברצף הן לא O(n^2): אם לולאה אחת רצה אחרי לולאה שנייה (לא מקוננת בתוכה), מספר הפעולות הוא n + n = 2n - וזה עדיין O(n), לא O(n^2). כפל קורה רק כשלולאה אחת בתוך לולאה אחרת.

בלבול בין "מספר פעולות מדויק" ל-Big-O: Big-O לא אומר "בדיוק 2n+3 פעולות" - הוא מתעלם מקבועים ומתאר רק את הצורה הכללית של הגידול.

🎓 זווית הבגרות

איך זה מופיע בבגרות: נושא היעילות שייך לשאלון 899271 (חמש יחידות) בלבד - הוא לא נכלל בחומר הלימוד של שאלון 899371 הבסיסי.

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

טעות נפוצה: לספור לולאות רצופות (לא מקוננות) כאילו הן מכפילות זו את זו במקום מצטברות - זה ההבדל בין O(n) ל-O(n^2) שהוזכר למעלה.

מה לזכור למבחן: ספרו כמה לולאות "מקוננות" (אחת בתוך השנייה) יש בקטע הקוד - מספר הלולאות המקוננות הוא בדרך כלל החזקה של n בתשובה.

8. תרגול

מה הסיבוכיות (Big-O) של הקוד הבא? הקלידו בפורמט O(1), O(n) או O(n^2).

Java

static void printAll(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
}

ומה הסיבוכיות של הקוד הזה?

Java

static void printGrid(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println(i + "," + j);
        }
    }
}

וזה? שימו לב היטב - הלולאות כאן לא מקוננות זו בתוך זו.

Java

static void printTwice(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
}

גישה ישירה לאיבר בודד במערך, ללא לולאה כלל (למשל arr[3]), היא בסיבוכיות...

לולאה אחת מקוננת בתוך לולאה אחרת, כשכל אחת מהן רצה n פעמים, נותנת סיבוכיות של...

→פרק 15 - תכנות מונחה עצמים מתקדם חזרה לרשימת הפרקים←