סיבוכיות זמן

הרצת תוכנית אורכת זמן. הידיעה מראש כמה זמן היא אורכת מועילה לכתיבת תוכניות יעילות. בתכנות, משך הזמן שנדרש להרצת תוכנית נקרא סיבוכיות זמן.

 לדוגמה

for(int i=0;i<5;i++{
   cout<<i<<endl;
}

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

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

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

קרא את המאמר שלהלן כדי ללמוד עוד על ניתוח סיבוכיות זמן.

סיבוכיות זמן