מבוא ליעילות מדעי המחשב לכיתה י״א

בנושא הזה 4 שיעורים. כך הם מתחילים:

1. זמן ריצה כפונקציה של אורך הקלט: ספירת פעולות

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

2. המקרה הטוב, הגרוע והממוצע

   לאותו אורך קלט, אלגוריתם יכול לרוץ מהר יותר או לאט יותר - לפי תוכן הקלט. המקרה הטוב: הקלט שעליו רצים הכי מעט צעדים; המקרה הגרוע: הכי הרבה; המקרה הממוצע: ממוצע על כל הקלטים.

3. סדר גודל O: קבוע, לוגריתמי, לינארי, ריבועי ומעריכי

   סימון O גדול מתאר איך זמן הריצה גדל כש-n גדל, בלי פרטים קטנים: מוחקים קבועים כופלים ואיברים מסדר נמוך. 3n + 5 הוא O(n); n²/2 + n הוא O(n²). הסדרים הנפוצים מהמהיר לאיטי: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).

4. ניתוח קוד נתון ושיפור זמן ריצה + חזרה

   כדי לנתח קוד נתון: מגדירים מה n, מוצאים את הצעד הבסיסי, וסופרים - כולל קריאות לפעולות! פעולה שנראית כמו לולאה אחת אבל קוראת בכל סיבוב לפעולה שהיא עצמה O(n) - היא O(n²).

→ רקורסיהחזרה מסכמת ←