שיעור 4: Big-O וניתוח סיבוכיות
דמיינו ספר טלפונים ענק ואתם מחפשים בו שם אחד: לדפדף עמוד-עמוד לוקח נצח, אבל אם הספר מסודר לפי א״ב יש דרך הרבה יותר חכמה. בשיעור הזה ניתן שם קצר לדפוסים כאלה — Big-O — דרך נוחה לתאר איך כמות העבודה גדלה עם כמות הנתונים. נכיר שלושה מקרים נפוצים: O(1), O(n) ו-O(n²), צעד-צעד, עם דוגמה לכל אחד.
Big-O זה פשוט לשאול: 'אם תכפיל/י את כמות הפריטים, כמה יותר עבודה זה ידרוש?'. אם עוברים על כל פריט פעם אחת, הכפלת הפריטים = פי 2 עבודה (קוראים לזה O(n)). אם משווים כל פריט מול כל פריט, הכפלת הפריטים = פי 4 עבודה (O(n²)). זהו — שם קצר לקצב שבו העבודה גדלה.
- ניתוח סיבוכיות
- הערכת כמות העבודה (זמן) והזיכרון שאלגוריתם דורש כפונקציה של גודל הקלט n.
- Big-O
- סימון לקצב הגדילה של אלגוריתם במקרה הגרוע, תוך התעלמות מקבועים ומאיברים זניחים.
- זמן ליניארי
- O(n): כמות העבודה גדלה ביחס ישר לגודל הקלט — מעבר אחד על כל איבר.
