סיבוכיות זמן - איך לקרוא ולהבין נוטציית Big O

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

הגדרה אינטואיטיבית

f(n) = O(g(n)) אומר ש-f גדל לכל היותר כמו g (עד כדי קבוע) כש-n גדול. זהו חסם עליון אסימפטוטי. מתעלמים מקבועים ומאיברים נמוכים יותר: 3n² + 5n + 7 = O(n²).

הסיבוכיות הנפוצות בסדר עולה

איך מחשבים סיבוכיות של קוד?

• פעולה בודדת (השמה, השוואה, אריתמטיקה) = O(1)
• לולאה שעוברת n פעמים = O(n)
• שתי לולאות מקוננות = O(n²)
• חצייה בכל איטרציה (כמו חיפוש בינארי) = O(log n)
• במקרה של מספר חלקים - לוקחים את הדומיננטי

// O(n²) - שתי לולאות מקוננות
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    console.log(i, j);
  }
}

// O(n + m) - לולאות נפרדות
for (let i = 0; i < n; i++) { /* ... */ }
for (let j = 0; j < m; j++) { /* ... */ }

Big O, Big Ω, Big Θ

• O(g) - חסם עליון (worst case או 'לכל היותר')
• Ω(g) - חסם תחתון ('לכל הפחות')
• Θ(g) - חסם הדוק (גם עליון וגם תחתון)