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

כאשר נשאלים על סיבוכיות האפשרויות הן בדרך כלל:

O(1) - כאשר יש מספר קבוע של פעולות

O(logn) - חיפוש בינארי

O(n) - חיפוש סידרתי: מעבר על מערך/מחסנית/תור/שרשרת חוליות

O(n^2) - לולאה מקוננת בד"כ

כאשר אנו עונים על סיבוכיות כזו או אחרת יש להתחשב בפעולות עזר / פעולות שאנו משתמשים בהם.

דוגמה ראשונה:

סריקת מערך בגודל n:

for(int i=0; i<arr.length;i++) //O(n)

{

// o(1)

}

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

דוגמה שנייה:

לולאת for מקוננת:

for(int i=0; i<n; i++) //O(n)

}

for(int j=0; j<m ; j++) //O(m)

{

//o(1)

}

}

בלולאה מקוננת אם גופי הלולאה מבצעים מספר קבוע של פעמים אז הסיבוכיות היא o(n*m).

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

דוגמה שלישית:

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

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

דוגמה רביעית:

פונקציה שסוכמת / סופרת את כמות הספרות.

יש להבין שהסיבוכיות כאן תלויה במספר הספרות, לכן הסיבוכיות היא O(n) כאשר n הוא מספר הספרות.