סיבוכיות זמן - איך לקרוא ולהבין נוטציית Big O
המדריך המעשי ל-Big O: מה הוא מודד, מה הוא מתעלם ממנו, ואיך לחשב סיבוכיות של קוד.
סימון Big O (O גדולה) מתאר איך זמן הריצה של אלגוריתם גדל ביחס לגודל הקלט n כש-n גדל לאינסוף. זה כלי השוואה בסיסי בין אלגוריתמים, וההבנה שלו קריטית בכל מבחן וראיון.
הגדרה אינטואיטיבית
f(n) = O(g(n)) אומר ש-f גדל לכל היותר כמו g (עד כדי קבוע) כש-n גדול. זהו חסם עליון אסימפטוטי. מתעלמים מקבועים ומאיברים נמוכים יותר: 3n² + 5n + 7 = O(n²).
הסיבוכיות הנפוצות בסדר עולה
| סיבוכיות | שם | דוגמה |
|---|---|---|
| O(1) | קבוע | גישה למערך לפי אינדקס |
| O(log n) | לוגריתמי | חיפוש בינארי |
| O(n) | לינארי | סריקת מערך |
| O(n log n) | לינארי-לוגריתמי | Merge Sort, Quick Sort |
| O(n²) | ריבועי | Bubble Sort, לולאות מקוננות |
| O(n³) | קובי | כפל מטריצות נאיבי |
| O(2ⁿ) | אקספוננציאלי | Fibonacci רקורסיבי נאיבי |
| O(n!) | פקטוריאלי | Traveling Salesman ב-brute force |
איך מחשבים סיבוכיות של קוד?
- פעולה בודדת (השמה, השוואה, אריתמטיקה) = 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) - חסם הדוק (גם עליון וגם תחתון)
טעות נפוצה: Big O לא מודד זמן ריצה ממש! O(n) יכול להיות איטי יותר מ-O(n²) על קלטים קטנים בגלל קבועים. Big O רלוונטי כש-n גדול.
שאלות נפוצות
מה בעצם מודדת נוטציית Big O?
היא מתארת את קצב הגידול של זמן הריצה או הזיכרון כפונקציה של גודל הקלט, כשהקלט גדל לאינסוף. היא אינה מודדת זמן בשניות ואינה מנבאת ביצועים על קלט קטן — היא עונה על השאלה כמה יותר גרוע יהיה המצב אם נכפיל את כמות הנתונים.
למה מתעלמים מקבועים ומאיברים נמוכים ב-Big O?
כי כשגודל הקלט גדל, האיבר בעל הקצב הגבוה ביותר משתלט על התוצאה. בביטוי 3n² + 100n + 500, עבור n גדול האיבר n² מכריע לחלוטין, ולכן הביטוי הוא O(n²). הקבועים תלויים בחומרה, בשפה ובמימוש, ולכן אינם מאפיינים את האלגוריתם עצמו.
איך מחשבים את הסיבוכיות של קטע קוד?
לולאות עוקבות מסתכמות — שתי לולאות זו אחר זו הן O(n)+O(n)=O(n). לולאות מקוננות מוכפלות — לולאה בתוך לולאה על אותו קלט היא O(n²). קריאה לפונקציה עולה כמו סיבוכיות הפונקציה. לבסוף לוקחים את האיבר הדומיננטי ומשמיטים קבועים. חלוקה חוזרת של הקלט לשניים מעידה בדרך כלל על גורם log n.