דילוג לתוכן המרכזי

סיכום רקורסיה ויעילות

מדעי המחשב לבגרות · 3 נושאים

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

רקורסיה

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

יעילות

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

1. פעולה רקורסיבית: מקרה בסיס וצעד

פעולה רקורסיבית

כשכותבים פעולה רקורסיבית לא צריך לדמיין את כל הקריאות. מספיק לענות על שתי שאלות: מה התשובה לקלט הקטן ביותר, ואיך בונים את התשובה לקלט גדול אם סומכים על כך שהקריאה על הקלט הקטן יותר מחזירה תשובה נכונה.
במדויק: לכל פעולה רקורסיבית שלושה חלקים: תנאי עצירה (מקרה הבסיס) - מחזירים תשובה בלי קריאה; קריאה רקורסיבית על קלט קטן יותר (n / 10, n - 1, lst.getNext(), tree.getLeft()); וצירוף - מה עושים עם הערך שחזר. יש פעולות רקורסיביות שמחזירות ערך, ויש פעולות void שמשנות מבנה או מדפיסות.

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

תבנית: פעולה רקורסיבית שמחזירה ערך

public static int sumDigits(int n)
{
    if (n < 10)                              // תנאי עצירה: ספרה אחת
        return n;
    return n % 10 + sumDigits(n / 10);       // צעד: הספרה האחרונה + סכום שאר הספרות
}

sumDigits(4071) מחזירה 12: 1 + sumDigits(407), כלומר 1 + 7 + 0 + 4. הקריאה האחרונה, sumDigits(4), עוצרת בתנאי העצירה.

מה מקטינים ומה תנאי העצירה, לפי הקלט

קלטהקריאה הרקורסיביתתנאי עצירה נפוץ
מספר שלםf(n / 10) או f(n - 1)ספרה אחת (n < 10), או n == 0
מספר שהשאלה מקטינהwhat(q, n - 1)התנאי שבשאלה, למשל mmm(q, n) מחזירה true
שרשרת חוליותf(lst.getNext())lst == null (שרשרת ריקה)
עץ בינריf(tree.getLeft()) ו-f(tree.getRight())tree == null, או עלה (אין בן שמאלי ואין בן ימני)

סוגי רקורסיה

סוגמה מאפיין אותובבגרות
רקורסיית זנבהקריאה הרקורסיבית היא הדבר האחרון, והערך שלה מוחזר כמו שהואreturn what(q, n - 1); (899271 קיץ 2025)
רקורסיית הלוך-חזוריש עבודה אחרי שהקריאה חוזרתwhat(lst, x) מחברת את החוליה ל-temp אחרי הקריאה (899271 קיץ 2024)
רקורסיה כפולהשתי קריאות רקורסיביות באותה קריאהfoo(tree.getLeft()) + foo(tree.getRight()) (899271 קיץ 2026)
רקורסיה הדדיתפעולה A קוראת ל-B, ו-B קוראת ל-A-

רקורסיית זנב אפשר לכתוב גם בלולאה: הפרמטר שמשתנה מקריאה לקריאה (כמו n) הוא משתנה הלולאה.

דרך הפתרון

כתיבת פעולה רקורסיבית

1.הגדרה במילים: "התשובה לקלט = משהו על החלק הראשון + התשובה לשאר". בעץ: "העץ תקין אם השורש תקין וגם שני תתי-העצים תקינים".
2.תנאי עצירה: הקלט הקטן ביותר שהפעולה יכולה לקבל (0, ספרה אחת, null, עלה). בודקים מה השאלה מבטיחה: "עץ שאינו ריק" - אין קריאה על null, ולכן בודקים hasLeft() / hasRight() לפני כל קריאה.
3.פרמטרים: מה משתנה מקריאה לקריאה (k - 1 כשיורדים שמאלה) ומה נשאר כמו שהוא (k כשיורדים ימינה, x בכל הקריאות).
4.צירוף: "כל" / "בכל מסלול" = &&, ואפשר להחזיר false מיד; "קיים" = ||; ספירה וסכום = +.
5.בדיקה: מריצים ביד על הדוגמה שבשאלה, ומוודאים שכל קריאה מתקרבת לתנאי העצירה.
שים לב

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

שים לב

כשתנאי העצירה הוא עלה ולא null, אסור לקרוא לפעולה על בן שאינו קיים. בפעולה foo של קיץ 2026 תנאי העצירה הוא עלה, ולכן על עץ ריק היא נכשלת; לכן השאלה מדברת על "עץ כלשהו שאינו ריק", והקוד בודק tree.getLeft() == null לפני כל קריאה.

דוגמה - בדיקה אם עץ הוא עץ K-שמאלי

"עץ K-שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותר K קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים).
בעץ שבשאלה (נסמן את הצמתים באותיות): לשורש A בן שמאלי B ובן ימני C. ל-B רק בן ימני D (עלה). ל-C בן שמאלי E ובן ימני G (עלה). ל-E בן שמאלי F ובן ימני H (שניהם עלים). העץ הזה אינו "עץ 1-שמאלי", כי במסלול A → C → E → F יש שתי קשתות שמאליות; הוא "עץ 2-שמאלי".
כתבו פעולה חיצונית ששמה isLeftK בשפת Java או IsLeftK בשפת C#, המקבלת עץ בינרי root מטיפוס שלם שאינו ריק, וערך K שאינו שלילי, ומחזירה true אם העץ הוא "עץ K-שמאלי", ואם לא - היא מחזירה false.

פתרון
1.הגדרה במילים: K הוא "התקציב" של קשתות שמאליות שעוד מותר להשתמש בהן בהמשך המסלול. העץ תקין אם תת-העץ השמאלי תקין עם K - 1, וגם תת-העץ הימני תקין עם K.
2.תנאי עצירה: העץ אינו ריק, ולכן לא קוראים על null. בעלה אין עוד קשתות: מחזירים true.
3.פרמטרים: ירידה שמאלה צורכת קשת אחת - k - 1; ירידה ימינה לא משנה את התקציב - k.
4.חריגה: אם יש בן שמאלי והתקציב כבר 0, מחזירים false מיד.
5.צירוף: "בכל מסלול" = שתי הבדיקות חייבות להצליח.
public static boolean isLeftK(BinNode<Integer> root, int k)
{
    if (root.hasLeft())
    {
        // ירידה שמאלה "צורכת" קשת שמאלית אחת
        if (k == 0 || !isLeftK(root.getLeft(), k - 1))
            return false;
    }
    if (root.hasRight())
    {
        // ירידה ימינה לא משנה את מספר הקשתות השמאליות
        if (!isLeftK(root.getRight(), k))
            return false;
    }
    return true;
}
6.בדיקה על העץ שבשאלה: isLeftK(A, 2) מחזירה true; isLeftK(A, 1) מחזירה false: A → C עם תקציב 1, C → E צורכת קשת (נשאר 0), ו-E → F צריכה קשת נוספת כשהתקציב 0. גם isLeftK(A, 0) מחזירה false, כבר בבן השמאלי B.
7.יעילות: כל צומת נבדק לכל היותר פעם אחת, ובכל צומת מספר קבוע של פעולות: O(n), כאשר n מספר הצמתים.
תשובה

רקורסיה עם "תקציב" K: אם יש בן שמאלי - אם K == 0 מחזירים false, אחרת בודקים אותו עם K - 1; בן ימני - בודקים עם אותו K; עלה - true. יעילות O(n).

2. מעקב אחר פעולה רקורסיבית

מעקב אחר רקורסיה

כל קריאה רקורסיבית היא "עותק" נפרד של הפעולה, עם פרמטרים ומשתנים משלו. הקריאה שקראה מחכה עד שהקריאה הפנימית תחזיר ערך, ורק אז ממשיכה מהנקודה שבה עצרה.
במדויק: במעקב אחר רקורסיה כותבים שורה לכל קריאה: הפרמטרים שהיא קיבלה, איזה מקרה התקיים, החישוב שלה במונחים של הקריאות הפנימיות (foo(9) + 1), והערך שהיא מחזירה. בשאלון כתוב לדוגמה: "המעקב יכלול בכל קריאה את הערכים של q, n ואת הערך המוחזר". בסוף כותבים במפורש מה הקריאה הראשונה מחזירה.

זו טבלת המעקב המוכרת מלולאות, אבל במקום שורה לכל סיבוב יש שורה לכל קריאה. בפעולה על שרשרת חוליות שורה לכל חוליה (ועוד אחת ל-null); בפעולה על עץ שורה לכל צומת.

לפני הקריאה ואחרי הקריאה

public static void upDown(int n)
{
    if (n > 0)
    {
        System.out.print(n + " ");   // לפני הקריאה: בדרך למטה
        upDown(n - 1);
        System.out.print(n + " ");   // אחרי הקריאה: בדרך חזרה
    }
}

upDown(3) מדפיסה 3 2 1 1 2 3.

איפה ההוראהמתי היא מתבצעת
לפני הקריאה הרקורסיביתבדרך למטה: בסדר הקריאות, מהראשונה לאחרונה
אחרי הקריאה הרקורסיביתבדרך חזרה: בסדר הפוך, מהקריאה האחרונה לראשונה

בפעולה what של 899271 קיץ 2024 הקריאה what(lst.getNext(), x) באה לפני הטיפול בחוליה, ולכן החוליות מטופלות מהאחרונה לראשונה.

דרך הפתרון

מעקב אחר רקורסיה: יורדים ואז עולים

1.שורה ראשונה: הקריאה מהשאלה והפרמטרים שלה.
2.בכל קריאה: בודקים איזה מקרה מתקיים. בתנאי עצירה הערך ידוע. בצעד כותבים את החישוב עם הקריאות הפתוחות (foo(9) + 1), ופותחים שורה לכל קריאה פנימית.
3.רקורסיה כפולה: קודם הקריאה השמאלית עד הסוף (עם כל הקריאות שלה), ורק אחריה הימנית.
4.בדרך חזרה: מציבים את הערכים שחזרו בחישוב של כל שורה, מלמטה למעלה.
5.התשובה: "הפעולה מחזירה ...". אם שואלים מה הפעולה עושה - מסתכלים מה כל קריאה תורמת, ומניחים שהקריאה הפנימית עושה את העבודה על החלק הקטן יותר.
שים לב

כשכתוב "אין צורך לעקוב אחר הפעולה mmm" או "אין צורך לעקוב אחר הפעולה what", משתמשים במה שמצאתם עליה בסעיף הקודם, בלי לפתוח אותה שוב. ב-what(q, 6) של קיץ 2025 מספיק לדעת ש-mmm בודקת רצף של לפחות n איברים שווים צמודים: mmm מחזירה false על 6, 5 ו-4 ו-true על 3, ולכן what(q, 6) מחזירה 3.

שים לב

ב-&& ו-|| הצד הימני לא מחושב כשהתוצאה כבר ידועה. בפעולה goo של קיץ 2026, goo(tree.getLeft()) && goo(tree.getRight()): אם הקריאה השמאלית מחזירה false, הקריאה הימנית לא מתבצעת בכלל, ואין לה שורה במעקב.

שים לב

פעולה שמוחקת חוליות ומחזירה את ראש השרשרת - התשובה היא השרשרת שהוחזרה. אחרי what(lst, 1) של קיץ 2024 המשתנה lst עדיין מפנה לחוליה 1 הראשונה, שנמחקה מהשרשרת שהוחזרה.

דוגמה א - רקורסיה כפולה על עץ בינרי

נתונה הפעולה foo בשפת Java או Foo בשפת C#:

public static int foo(BinNode<Integer> tree)
{
    if (tree.getLeft() == null && tree.getRight() == null)
        return 0;
    if (tree.getLeft() == null)
        return foo(tree.getRight()) + 1;
    if (tree.getRight() == null)
        return foo(tree.getLeft()) - 1;
    return foo(tree.getLeft()) + foo(tree.getRight());
}

העץ tree: השורש 5, ולו רק בן ימני 9. ל-9 רק בן ימני 7. ל-7 בן שמאלי 0 ובן ימני 3 (שניהם עלים).
בצעו מעקב אחרי הפעולה foo והעץ, וכתבו מה הפעולה מחזירה. יש להציג את המעקב.

פתרון
1.ארבעה מקרים: עלה - 0; רק בן ימני - foo(ימני) + 1; רק בן שמאלי - foo(שמאלי) - 1; שני בנים - סכום שתי הקריאות.
2.בדרך למטה: לכל צומת בודקים את המקרה ופותחים קריאה.
קריאהמצב הצומתחישובערך מוחזר
foo(5)רק בן ימני (9)foo(9) + 12
foo(9)רק בן ימני (7)foo(7) + 11
foo(7)שני בניםfoo(0) + foo(3)0
foo(0)עלה-0
foo(3)עלה-0
3.בדרך חזרה: foo(0) = 0 ו-foo(3) = 0, לכן foo(7) = 0 + 0 = 0; foo(9) = 0 + 1 = 1; foo(5) = 1 + 1 = 2.
4.מה היא מחזירה בכלל: כל צומת עם בן ימני בלבד תורם 1, כל צומת עם בן שמאלי בלבד תורם -1, ועלה או צומת עם שני בנים תורמים 0. כאן יש שני צמתים עם בן ימני בלבד (5 ו-9).
תשובה

הפעולה מחזירה 2.

דוגמה ב - רקורסיית הלוך-חזור שמוחקת חוליות

נתונה הפעולה what בשפת Java או What בשפת C#:

public static Node<Integer> what(Node<Integer> lst, int x)
{
    if (lst == null)
        return null;
    Node<Integer> temp = what(lst.getNext(), x);
    if (lst.getValue() == x)
        return temp;
    lst.setNext(temp);
    return lst;
}

נתונה שרשרת חוליות lst מטיפוס שלם: 1 → 3 → 5 → 3 → 1 → 9 → 4 → null (משמאל לימין: 1, 3, 5, 3, 1, 9, 4).
עקבו אחר הפעולה what(lst, 1), והציגו את השרשרת שהפעולה מחזירה.

פתרון
1.הקריאה לפני הטיפול: what(lst.getNext(), x) באה לפני הבדיקה של החוליה. לכן הקריאות יורדות עד null, והחוליות מטופלות בדרך חזרה, מהאחרונה לראשונה.
2.בכל קריאה: temp הוא ההמשך שכבר "נוקה". אם ערך החוליה הוא x - מחזירים את temp (מדלגים על החוליה). אחרת - setNext(temp) ומחזירים את החוליה.
קריאה על חוליהtemp שחזרהערך הוא 1?מוחזר
null--null
4nullלא4
94לא9 → 4
1 (החמישית)9 → 4כן9 → 4
3 (הרביעית)9 → 4לא3 → 9 → 4
53 → 9 → 4לא5 → 3 → 9 → 4
3 (השנייה)5 → 3 → 9 → 4לא3 → 5 → 3 → 9 → 4
1 (הראשונה)3 → 5 → 3 → 9 → 4כן3 → 5 → 3 → 9 → 4
3.בדיקה בהרצה: השרשרת שהוחזרה מודפסת 3 -> 5 -> 3 -> 9 -> 4 -> null. ההרצה מראה גם ש-lst עצמו עדיין מתחיל בחוליה 1.
4.מה היא עושה: מוחקת מהשרשרת את כל החוליות שערכן x, בלי לשנות את סדר השאר, ומחזירה את הראש החדש.
תשובה

הפעולה מחזירה את השרשרת 3 → 5 → 3 → 9 → 4 → null (שתי החוליות עם הערך 1 הוסרו).

3. יעילות: סיבוכיות זמן ריצה O

סיבוכיות של פעולה על מבנה נתונים

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

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

מקרה גרוע ומקרה טוב בשאלות הבגרות

פעולההמקרה הגרועהמקרה הטוב
guess (קיץ 2024): לכל חוליה מוחקת מההמשך את הכפולים שלהכל הערכים שונים, אף חוליה לא נמחקת: O(n²)כל הערכים שווים, הקריאה הראשונה מוחקת הכול: O(n)
what(q, n) (קיץ 2025): יורדת מ-n עד אורך הרצף הארוך ביותראין שני איברים צמודים שווים, n קריאות: O(n²)כל האיברים שווים, קריאה אחת: O(n)

הסיבוכיות שעונים בשאלה היא של המקרה הגרוע. כותבים מהו הקלט הגרוע, ולמה הוא הגרוע.

סכומים שחוזרים בנימוק

מה קורההסכוםסדר גודל
n סיבובים, O(1) בכל סיבובn · 1O(n)
n + 1 קריאות (אחת לכל חוליה ועוד אחת ל-null)n + 1O(n)
k סבבים, בכל סבב מעבר על עד n איבריםk · nO(k·n), ובמקרה הגרוע k = n: O(n²)
בכל סבב מעבר על מה שנשאר: n − 1, n − 2, ..., 1, 0n(n − 1) / 2O(n²)
חלקים שבאים זה אחרי זה: O(n²), ואחריו O(n), ואחריו O(n)משאירים את הגדולO(n²)

גם כשבכל סבב עוברים על פחות איברים, הסכום (n − 1) + (n − 2) + ... + 1 הוא בערך חצי מ-n², ולכן O(n²) ולא O(n).

יעילות של פעולה רקורסיבית

מבנה הקריאותמספר קריאותעבודה בכל קריאהסיבוכיותבבגרות
קריאה אחת על ההמשךn + 1O(1)O(n)what(lst, x), קיץ 2024
קריאה אחת על n - 1עד nקריאה לפעולה ב-O(n)O(n²)what(q, n), קיץ 2025
קריאה אחת על ההמשךn + 1קריאה לפעולה על ההמשך: n − 1, n − 2, ..., 0O(n²)guess, קיץ 2024
שתי קריאות, על שני תתי-העציםכל צומת פעם אחתO(1)O(n)isLeftK, קיץ 2025

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

דרך הפתרון

סיבוכיות של רקורסיה: קריאות כפול עבודה

1.מה n: "n - מספר החוליות ב-lst".
2.כמה קריאות במקרה הגרוע: בכל קריאה הקלט קטן באחד? יש n קריאות (ועוד אחת לתנאי העצירה). בעץ: כמה פעמים כל צומת מבוקר.
3.העבודה בקריאה אחת, בלי הקריאה הרקורסיבית: פעולות הממשק O(1). קריאה לפעולה אחרת - הסיבוכיות שלה, על הקלט שהיא מקבלת באותה קריאה.
4.מכפילים, או מחברים כשהעבודה משתנה: n · O(1) = O(n); n · O(n) = O(n²); (n − 1) + (n − 2) + ... + 0 = O(n²).
5.נימוק: "יש n + 1 קריאות, בכל אחת מספר קבוע של פעולות, לכן O(n)".
שים לב

קריאה לפעולה אחרת בתוך רקורסיה אינה צעד אחד. guess של קיץ 2024 קוראת בכל חוליה ל-what על ההמשך, ו-what עוברת על כל ההמשך. מי שסופר רק את n הקריאות של guess וכותב O(n) - טועה: הסיבוכיות O(n²).

שים לב

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

שים לב

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

דוגמה א - סיבוכיות של רקורסיה על שרשרת

נתונה הפעולה what בשפת Java או What בשפת C#, שמוחקת משרשרת חוליות lst את כל החוליות שערכן x ומחזירה את ראש השרשרת:

public static Node<Integer> what(Node<Integer> lst, int x)
{
    if (lst == null)
        return null;
    Node<Integer> temp = what(lst.getNext(), x);
    if (lst.getValue() == x)
        return temp;
    lst.setNext(temp);
    return lst;
}

מהי סיבוכיות הפעולה what? נמקו את תשובתכם.

פתרון
1.n: מספר החוליות ב-lst.
2.מספר הקריאות: כל קריאה קוראת לעצמה פעם אחת בלבד, על lst.getNext(). הקריאות יורדות חוליה אחר חוליה עד null: n קריאות על החוליות ועוד אחת על null, כלומר n + 1. כאן אין הבדל בין מקרה גרוע לטוב: תמיד עוברים על כל השרשרת.
3.עבודה בכל קריאה: בדיקת null, getValue(), השוואה, setNext(temp) ו-return - מספר קבוע של פעולות, O(1).
4.סך הכול: (n + 1) · O(1) = O(n).
5.בדיקה בהרצה: על שרשרות באורך 100, 200, 400, 800, 1600 היו 101, 201, 401, 801, 1601 קריאות.
תשובה

O(n), כאשר n הוא מספר החוליות בשרשרת: קריאה רקורסיבית אחת לכל חוליה (ועוד אחת ל-null), ובכל קריאה עבודה קבועה.

דוגמה ב - לולאה שעוברת בכל סבב על מה שנשאר

נתונה המחלקה Order (הזמנה) עם התכונות id (מספר זהות של הלקוח) ו-count (כמות המוצרים). הפעולה uniteOrders בשפת Java או UniteOrders בשפת C# מקבלת תור הזמנות qOrder, שבו אותו לקוח יכול להופיע כמה פעמים, ומחזירה תור חדש שבו לכל לקוח הזמנה אחת עם סך כל המוצרים שלו:

public static Queue<Order> uniteOrders(Queue<Order> qOrder)
{
    Queue<Order> result = new Queue<Order>();
    while (!qOrder.isEmpty())
    {
        Order first = qOrder.remove();          // הזמנה של לקוח חדש
        int total = first.getCount();
        Queue<Order> temp = new Queue<Order>();
        while (!qOrder.isEmpty())               // מעבר על שאר ההזמנות
        {
            Order o = qOrder.remove();
            if (o.getId() == first.getId())
                total += o.getCount();          // אותו לקוח - מצרפים
            else
                temp.insert(o);                 // לקוח אחר - שומרים לסבב הבא
        }
        qOrder = temp;
        result.insert(new Order(first.getId(), total));
    }
    return result;
}

מהי סיבוכיות זמן הריצה של הפעולה? נמקו את תשובתכם.

פתרון
1.n: מספר ההזמנות בתור qOrder.
2.המחיר לסיבוב: isEmpty(), remove(), insert(x) ופעולות get - כל אחת O(1).
3.סבב של הלולאה החיצונית: מוציא הזמנה אחת, ואז הלולאה הפנימית עוברת על כל ההזמנות שנשארו בתור.
4.המקרה הגרוע: כל ההזמנות של לקוחות שונים. אז בכל סבב יוצאת מהתור הזמנה אחת בלבד, והלולאה הפנימית עוברת על n − 1, n − 2, ..., 1, 0 הזמנות.
5.סך הכול: (n − 1) + (n − 2) + ... + 1 = n(n − 1) / 2, כלומר O(n²).
6.בדיקה בהרצה: על התור (7,20), (4,3), (7,15), (9,8), (7,30), (4,6) הלולאה הפנימית עברה על 5, 2 ו-0 הזמנות, והתוצאה (7,65), (4,9), (9,8). על n הזמנות של לקוחות שונים (n = 100, 200, 400, 800) היו בדיוק n(n − 1) / 2 סיבובים פנימיים: 4950, 19900, 79800, 319600.
תשובה

O(n²): לכל לקוח מעבר על כל ההזמנות שנותרו, (n − 1) + (n − 2) + ... + 1 במקרה הגרוע.

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

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