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

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

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

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

מה בודקים בבגרות במדעי המחשב

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

1. השאלונים, המיקוד, בחירת השאלות ושפת התכנות

שני שאלונים בכתב

במדעי המחשב יש שתי רמות: 3 יחידות ו-5 יחידות. מי שלומד 5 יחידות נבחן קודם ברמה של 3, ואחר כך בשאלון השלמה.
במדויק: 899371 - היסודות (יחידות 1-2): משתנים, תנאים, לולאות, מערכים, פעולות ומחלקות. 899271 - ההשלמה ל-5 יחידות: מבני נתונים (רקורסיה, יעילות, תור, שרשרת חוליות, עץ בינרי) ונושא בחירה אחד מתוך שלושה: אלגוריתמים, מודלים חישוביים או תכנות מונחה עצמים. היחידה השלישית היא מטלת ביצוע פנימית (899373); נבחנים אקסטרניים כותבים במקומה את 899372. שאלון ההשלמה ל-5 יחידות הוא שאלון חוסם: מי שמקבל בו פחות מ-55 נשאר עם ציון של 3 יחידות.

המשקלות לפי מבנה הבחינות של הפיקוח: ב-899371 הציון השנתי 30% והבחינה 70%; ב-899271 (מקיץ 2025) הציון השנתי 40% והבחינה החיצונית 60%.

מבנה השאלונים כפי שהוא מודפס

שאלוןמה נבחןמבנהמשך
899371יסודותפרק ראשון: 2 מתוך 3 שאלות, 20 נקודות לכל שאלה. פרק שני: 2 מתוך 3, 30 נקודות לכל שאלהשעתיים וחצי
899271מבני נתונים ונושא בחירהפרק ראשון (מבני נתונים): 2 מתוך 3, 25 נקודות לכל שאלה. פרק שני: 2 מתוך 3 שאלות במסלול שלמדתם, 25 נקודות לכל שאלהשלוש שעות

בפרק השני של 899271 יש שלושה מסלולים: אלגוריתמים (שאלות 4-6), מודלים חישוביים (שאלות 7-9) ותכנות מונחה עצמים (שאלות 10-12). על הכריכה של המחברת רושמים את שם המסלול.

מה במיקוד תשפ"ז ומה לא

שאלוןבמיקודלא במיקוד
899371מושגי יסוד (כולל char, double, מחרוזות ופעולות של מחרוזות), ביצוע מותנה, ביצוע חוזר, מערכים וחיפוש סדרתי, מערך דו-ממדי, תכנות מונחה עצמים כולל מחלקה מורכבתחיפוש בינרי, מיון הכנסה, מיון מיזוג, השוואת יעילות החיפושים, מערך של עצמים
899271, מבני נתוניםרקורסיה, מבוא ליעילות, תור, רשימה חד-כיוונית (שרשרת חוליות), עצים בינריים: מבנה, מינוח, החוליה הבינרית וסריקותמחסנית, רשימה דו-כיוונית, מימוש מבני נתונים, עץ חיפוש בינרי
אלגוריתמיםפרקים 1-8: גרפים, ייצוג, מסלולים קצרים (BFS, משקלות אי-שליליים, משקלות שליליים), סריקה לעומק, מיון טופולוגי, עץ פורש מינימליזרימה ברשתות, קידוד ודחיסה
מודלים חישובייםתיאור מערכות, אוטומט סופי דטרמיניסטי, מילים ושפות, מודלים נוספים של אוטומט סופי, אוטומט מחסנית דטרמיניסטי, מכונת טיורינגאוטומט מחסנית לא דטרמיניסטי, תכונות הסגירות של השפות חופשיות ההקשר
תכנות מונחה עצמיםפרקים 1-5, כולל מערך של עצמים, ירושה ופולימורפיזםממשקים, שפות תכנות
שים לב

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

דרך הפתרון

לפני שעונים

1.בודקים את כללי המענה של המועד. המבנה משתנה: בקיץ 2024 שני השאלונים נבנו כ-4 שאלות מתוך כל השאלות (25 נקודות לכל שאלה), ובקיץ 2026 פרסם משרד החינוך הנחיות חדשות למענה, שגוברות על מה שמודפס בשאלון.
2.שפה אחת: את כל התוכניות כותבים ב-Java או ב-C#, לא מערבבים.
3.בוחרים שאלות לפי מה שאתם בטוחים בו. בשאלה עם כמה סעיפים קוראים את כולם לפני שבוחרים: סעיף מאוחר נשען לפעמים על פעולה מסעיף מוקדם.
4.ב-899271 עונים בפרק השני רק מהמסלול שלמדתם, ורושמים את שם המסלול על הכריכה.
שים לב

בשאלון כתוב: "לא יורדו נקודות אם תכתבו בתוכניות אות גדולה במקום אות קטנה או להפך". כלומר isEmpty ו-IsEmpty שתיהן מתקבלות. מה שכן חשוב: שפה אחת לכל הבחינה.

שים לב

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

דוגמה - בחירת השאלות לפי ההנחיות של קיץ תשפ"ו

בקיץ תשפ"ו (2026) פרסם משרד החינוך הנחיות חדשות למענה בשאלון 899371: "יש לענות על 4 שאלות מתוך 6 השאלות במבחן. לכל שאלה - 25 נקודות."
בשאלון מודפס: פרק ראשון - 2 מתוך שאלות 1-3 (20 נקודות לכל שאלה), פרק שני - 2 מתוך שאלות 4-6 (30 נקודות לכל שאלה).
תלמיד בטוח בשאלות 1, 2 ו-3 (פרק ראשון) ובשאלה 5 (פרק שני). על אילו שאלות הוא יכול לענות, וכמה נקודות שווה כל שאלה?

פתרון
1.מה גובר: ההנחיות של המועד גוברות על המבנה המודפס.
2.כמה שאלות: 4 שאלות מתוך 6, בלי הגבלה לפי פרקים.
3.הבחירה: שאלות 1, 2, 3 ו-5 מותרות. לפי המבנה המודפס היה מותר לענות רק על שתיים מבין 1-3.
4.הנקודות: 25 לכל שאלה, כלומר 4 × 25 = 100.
תשובה

הוא יכול לענות על שאלות 1, 2, 3 ו-5: לפי ההנחיות של קיץ תשפ"ו עונים על 4 שאלות מתוך 6, מכל הפרקים. כל שאלה שווה 25 נקודות, ובסך הכול 100.

2. שאלת מעקב: טבלת מעקב, פלט ומה הפעולה מבצעת

טבלת מעקב

בשאלת מעקב אתם "משחקים מחשב": מבצעים את הקוד בעצמכם, הוראה אחר הוראה, ורושמים מה קורה למשתנים. הטבלה היא הדרך להראות לבודק שעשיתם את זה נכון.
במדויק: טבלת מעקב היא "כלי עזר שמאפשר לעקוב אחר קטע קוד ולבדוק את נכונותו". יש בה עמודה לכל משתנה (ולפעמים לתנאי, למשל y < z, או לביטוי, למשל arr[i]), וכל שורה היא סיבוב אחד של הלולאה. בשאלה כתוב בדיוק אילו עמודות לכלול, ובסוף כותבים במפורש מה הפעולה מחזירה או מה היא מדפיסה.

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

מה כל שאלת מעקב מבקשת

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

בניית טבלת מעקב

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

מה הפעולה מבצעת

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

הסדר של ההוראות בתוך הלולאה קובע. בפעולה what של 899371 קיץ 2025, בסיבוב שבו y נעשה -1, קודם מעדכנים את x (שנשאר 7) ורק אחר כך מאפסים את y. מי שמחליף את הסדר מקבל טבלה אחרת.

שים לב

"מה הפעולה מבצעת" היא שאלה על המטרה, לא על הדוגמה. בפעולה mmm של 899271 קיץ 2025 המספר 1 מופיע 4 פעמים בתור, אבל mmm(q, 4) מחזירה false: היא בודקת רצף של איברים שווים צמודים, לא כמה פעמים מספר מופיע.

דוגמה - מעקב אחר סכום רץ ומקסימום במערך

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

public static int what(int[] arr)
{
    int y = 0;
    int x = arr[0];
    for (int i = 0; i < arr.length; i++)
    {
        y += arr[i];
        x = Math.max(x, y);
        y = Math.max(y, 0);
    }
    return x;
}

נתון המערך arr = {3, 4, -8, 10, -6, 8}.
עקבו בעזרת טבלת מעקב אחר הפעולה what(arr), וכתבו מה הפעולה מחזירה. בטבלת המעקב יש לכלול עמודה בעבור כל אחד מן המשתנים i, y, x.

פתרון
1.אתחול: y = 0, x = arr[0], כלומר x = 3.
2.בכל סיבוב שלוש הוראות לפי הסדר: מוסיפים את arr[i] ל-y; x מקבל את הגדול מבין x ו-y; אם y שלילי - הוא מתאפס.
שלבiarr[i]y אחרי y += arr[i]xy בסוף הסיבוב
אתחול---30
103333
214777
32-8-170
4310101010
54-64104
658121212
סיום6--1212
3.הסיום: כש-i = 6 התנאי i < 6 לא מתקיים, והפעולה מחזירה את x.
4.מה היא מבצעת: y הוא סכום רץ שמתאפס כשהוא שלילי, ו-x שומר את הסכום הגדול ביותר שהגיע אליו. לכן הפעולה מחזירה את הסכום הגדול ביותר של רצף איברים צמודים, כאן 10 + (-6) + 8.
תשובה

הפעולה מחזירה 12 (הסכום הגדול ביותר של רצף איברים צמודים: 10 + (-6) + 8).

3. כתיבת פעולה: כותרת, אלגוריתם וקוד

שאלת כתיבה

רוב הנקודות בבגרות הן על קוד שאתם כותבים. השאלה מתארת בדיוק מה הפעולה מקבלת ומה היא מחזירה או מדפיסה, ונותנת לה שם בשתי השפות: ככה אתם יודעים מה הכותרת צריכה להיות.
במדויק: פעולה חיצונית היא פעולה סטטית (public static) מחוץ למחלקה, שמקבלת את כל מה שהיא צריכה כפרמטרים. פעולה פנימית נכתבת בתוך מחלקה ועובדת על התכונות של העצם. השם בשאלה כתוב בשתי השפות, למשל "פעולה חיצונית ששמה isNarc בשפת Java או IsNarc בשפת C#". "מחזירה" פירושו return; "מדפיסה" פירושו הדפסה, והפעולה מסוג void.

המילים בשאלה ומה הן אומרות בקוד

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

Java מול C#: ההבדלים שחוזרים בבגרות

מהJavaC#
ערך בוליאניbooleanbool
מחרוזתStringstring
אורך מערךarr.lengtharr.Length
אורך מחרוזת, תו במקום is.length(), s.charAt(i)s.Length, s[i]
הדפסהSystem.out.println(x)Console.WriteLine(x)
קליטת מספר שלםscan.nextInt()int.Parse(Console.ReadLine())
מקסימוםMath.max(a, b)Math.Max(a, b)
תור של מספרים שלמיםQueue<Integer>Queue<int>
שמות פעולותisEmpty(), getValue()IsEmpty(), GetValue()
דרך הפתרון

כתיבת פעולה בארבעה צעדים

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

כשמפרקים מספר לספרות בעזרת % 10 ו-/ 10, עובדים על עותק (temp). מי שמחלק את num עצמו נשאר בסוף עם 0, ואין עם מה להשוות.

שים לב

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

דוגמה - בדיקה אם מספר הוא נרקיסיסטי

מספר חיובי num ייקרא "מספר נרקיסיסטי" אם כשמעלים כל אחת מהספרות שלו בחזקת כמות הספרות שלו ומחברים את התוצאות, מתקבל num. למשל 407: 4³ + 0³ + 7³ = 64 + 0 + 343 = 407. לעומת זאת 58 אינו נרקיסיסטי: 5² + 8² = 89.
כתבו פעולה חיצונית ששמה isNarc בשפת Java או IsNarc בשפת C#, המקבלת מספר שלם num הגדול מ-0. הפעולה מחזירה true אם המספר נרקיסיסטי, אחרת היא מחזירה false.

פתרון
1.כותרת: מקבלת int ומחזירה ערך בוליאני.
2.מעבר ראשון על הספרות: סופרים כמה ספרות יש (len), על העותק temp.
3.מעבר שני: לכל ספרה digit = temp % 10 מחשבים digit בחזקת len בלולאה של כפל, ומוסיפים ל-sum.
4.התשובה: מחזירים sum == num.
public static boolean isNarc(int num)
{
    int len = 0;
    int temp = num;
    while (temp > 0)
    {
        len++;
        temp = temp / 10;
    }
    int sum = 0;
    temp = num;
    while (temp > 0)
    {
        int digit = temp % 10;
        int power = 1;
        for (int i = 1; i <= len; i++)
        {
            power = power * digit;
        }
        sum = sum + power;
        temp = temp / 10;
    }
    return sum == num;
}
5.בדיקה: 407: len = 3, והסכום 343 + 0 + 64 = 407, לכן true. 58: len = 2, והסכום 64 + 25 = 89, לכן false.
תשובה

סופרים ספרות (len), מחברים כל ספרה בחזקת len, ומחזירים sum == num.

4. כתיבת מחלקה: תכונות, פעולה בונה ופעולות

מחלקה ועצם

מחלקה היא תבנית: היא קובעת אילו נתונים יש לכל עצם (התכונות) ומה אפשר לעשות איתו (הפעולות). עצם הוא מופע אחד שנבנה מהתבנית בעזרת new.
במדויק: תכונות - משתנים פרטיים (private) של העצם. פעולה בונה - פעולה בשם המחלקה, בלי טיפוס מוחזר, שמאתחלת את כל התכונות. get / set - פעולות שמחזירות או משנות תכונה; בשאלות כתוב בדרך כלל "הניחו שקיימות פעולות get/Get ו-set/Set לתכונות המחלקה". פעולה פנימית - פעולה בתוך המחלקה שמשתמשת בתכונות. מחלקה מורכבת - מחלקה שאחת התכונות שלה היא עצם של מחלקה אחרת.

השלד של מחלקה

public class Student
{
    private String name;   // תכונות
    private int grade;

    public Student(String name, int grade)   // פעולה בונה
    {
        this.name = name;
        this.grade = grade;
    }

    public int getGrade() { return grade; }                 // get
    public void setGrade(int grade) { this.grade = grade; } // set

    public boolean passed()   // פעולה פנימית
    {
        return grade >= 55;
    }

    public String toString()
    {
        return name + " " + grade;
    }
}
דרך הפתרון

כתיבת פעולה בונה ופעולות של המחלקה

1.תכונות: בדיוק השמות והטיפוסים שבשאלה.
2.פעולה בונה: מקבלת את מה שהשאלה מונה. תכונה שלא מתקבלת כפרמטר מקבלת את הערך שהשאלה קובעת (למשל "בכמות של יחידה אחת" - quantity = 1).
3.פעולה פנימית: ניגשת לתכונות ישירות, וקוראת לפעולה פנימית אחרת כשהשאלה מבקשת.
4.פעולה חיצונית שמקבלת עצמים: ניגשת לתכונות רק דרך get.
שים לב

"גבוה מ-170" הוא > 170, ו"10 יחידות לפחות" הוא >= 10. במחלקה Order של קיץ 2026, הזמנה של 10 יחידות ב-17.00 ש"ח (170 בדיוק) לא מקבלת משלוח חינם.

שים לב

בקיץ 2026 נכתב בהנחיות: "בבחינה יש שאלה אחת בלבד בנושא מחלקה מורכבת (מחלקה שאחת מתכונותיה היא אובייקט של מחלקה אחרת)".

דוגמה - פעולה בונה ומחיר הזמנה עם משלוח

נתונה המחלקה Order, המייצגת הזמנה של מוצר, ולה ארבע תכונות: productID (קוד המוצר, שלם), price (המחיר, ממשי), quantity (כמות היחידות, שלם) ו-delivery (האם כולל משלוח עד הבית, בוליאני).
לקוח שהזמין משלוח משלם תוספת של 100 ש"ח. אם הוזמנו 10 יחידות לפחות, ונוסף על כך סכום ההזמנה (בלי המשלוח) גבוה מ-170.00 ש"ח - המשלוח חינם.
א. כתבו פעולה בונה המקבלת productID ו-price, ויוצרת הזמנה של יחידה אחת עם משלוח עד הבית.
ב. (1) כתבו פעולה פנימית totalPrice / TotalPrice המחזירה את סכום ההזמנה בלי דמי משלוח. (2) כתבו פעולה פנימית totalCost / TotalCost המחזירה את הסכום כולל דמי משלוח. יש להשתמש בפעולה מתת-סעיף (1).

פתרון
1.א: productID ו-price מהפרמטרים; quantity = 1; delivery = true.
2.ב(1): מחיר ליחידה כפול מספר היחידות.
3.ב(2): sum = totalPrice(). המשלוח חינם אם quantity >= 10 וגם sum > 170.00. מוסיפים 100 רק אם delivery == true והמשלוח לא חינם.
private int productID;
private double price;
private int quantity;
private boolean delivery;

public Order(int productID, double price)
{
    this.productID = productID;
    this.price = price;
    this.quantity = 1;
    this.delivery = true;
}

public double totalPrice()
{
    return price * quantity;
}

public double totalCost()
{
    double sum = totalPrice();
    boolean freeDelivery = quantity >= 10 && sum > 170.00;
    if (delivery && !freeDelivery)
        sum = sum + 100;
    return sum;
}
4.בדיקה: יחידה אחת ב-20.0 עם משלוח - 120.0. עשר יחידות ב-20.0 - 200 > 170, ולכן 200.0 בלי תוספת. עשר יחידות ב-17.0 - 170 אינו גבוה מ-170, ולכן 270.0.
תשובה

א. productID ו-price מהפרמטרים, quantity = 1, delivery = true.
ב. (1) return price * quantity; (2) sum = totalPrice(); אם delivery וגם לא (quantity >= 10 וגם sum > 170) - מוסיפים 100.

5. שאלת יעילות: סיבוכיות זמן ריצה ונימוק

סיבוכיות זמן ריצה

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

בשאלון 899271 כמעט כל שאלה על תור, שרשרת או עץ נגמרת ב"מהי סיבוכיות זמן הריצה של הפעולה? נמקו את תשובתכם".

סדרי הגודל הנפוצים

סדר גודלמתידוגמה
O(1)מספר קבוע של צעדים, לא תלוי ב-nhead(), insert(x), remove(), getNext()
O(n)מעבר אחד על n האיברים, צעד קבוע לכל איברסיבוב של תור, סריקה של שרשרת, ביקור בכל צומת בעץ
O(n²)לולאה בתוך לולאה על n, או n קריאות לפעולה שעולה O(n)השוואה של כל איבר לכל האחרים
O(log n)הקלט נחצה בכל צעדn = n / 2 עד שמגיעים ל-1
דרך הפתרון

חישוב הסיבוכיות והנימוק

1.מה n: "n - מספר האיברים בתור q".
2.המחיר של כל הוראה: פעולות הממשק O(1); קריאה לפעולה אחרת - הסיבוכיות שלה.
3.כמה סיבובים במקרה הגרוע: לכל לולאה, ולכל רמה של רקורסיה.
4.מכפילים ומחברים: סיבובים × מחיר לסיבוב; מחברים חלקים שבאים זה אחרי זה, ומשאירים את הגדול.
5.כותבים: הסיבוכיות, ומשפט נימוק: כמה סיבובים ומה מחיר כל סיבוב.
שים לב

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

שים לב

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

דוגמה א - סיבוב אחד של תור

לפניכם הפעולה mmm בשפת Java או Mmm בשפת C#, המקבלת תור q ובו מספרים הגדולים מ-0, ומספר שלם z הגדול מ-0:

public static boolean mmm(Queue<Integer> q, int z)
{
    q.insert(0);
    int num = q.head();
    int y = 0;
    while (q.head() > 0)
    {
        if (y < z)
        {
            if (q.head() == num)
            {
                y++;
            }
            else
            {
                num = q.head();
                y = 1;
            }
        }
        q.insert(q.remove());
    }
    q.remove();
    return y == z;
}

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

פתרון
1.n: מספר האיברים בתור q.
2.המחיר לסיבוב: head(), insert(x), remove() והשוואות - כל אחת O(1).
3.מספר הסיבובים: הפעולה מכניסה 0 לסוף התור ומסובבת אותו: בכל סיבוב איבר אחד עובר מהראש לסוף, עד שה-0 מגיע לראש. זה בדיוק n סיבובים.
4.סך הכול: n · O(1), ועוד מספר קבוע של הוראות מחוץ ללולאה - O(n).
תשובה

O(n) - מעבר אחד על n איברי התור, O(1) לכל איבר.

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

לפניכם הפעולה what בשפת Java או What בשפת C#, המקבלת תור q ובו מספרים הגדולים מ-0, ואת גודל התור n. הפעולה mmm (מהדוגמה הקודמת) היא O(n), ומחזירה true אם יש בתור רצף של לפחות z איברים שווים צמודים.

public static int what(Queue<Integer> q, int n)
{
    if (mmm(q, n))
        return n;
    return what(q, n - 1);
}

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

פתרון
1.מחיר של קריאה אחת: קריאה אחת ל-mmm, O(n), ועוד מספר קבוע של הוראות.
2.מספר הקריאות: n יורד ב-1 בכל קריאה, עד לאורך הרצף הארוך ביותר. המקרה הגרוע: אין שני איברים צמודים שווים, והרקורסיה יורדת עד 1 - n קריאות.
3.סך הכול: n קריאות × O(n) לכל קריאה = O(n²).
תשובה

O(n²) במקרה הגרוע: עד n קריאות רקורסיביות, בכל אחת mmm ב-O(n).

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

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

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