שיעור 3: מה זה 'יעיל'? סופרים צעדים

ברוך/ה הבא/ה! כבר ראינו שאלגוריתם הוא רשימת צעדים. עכשיו נשאל שאלה חדשה וחשובה: מתי אלגוריתם נחשב 'יעיל'? התשובה הפשוטה: כשהוא עושה פחות צעדים כדי להגיע לאותה תוצאה. כדי להרגיש את זה, נלמד פעולה קטנטנה אחת — לספור כמה צעדים אלגוריתם עושה — ונראה מה קורה לספירה הזו כשהרשימה גדלה. אין צורך בידע מוקדם

'יעיל' פירושו 'עושה פחות עבודה לאותה תוצאה'. כמו למצוא שם בספר טלפונים: לדפדף דף-דף זה הרבה צעדים, אבל קפיצה חכמה לאמצע חוסכת המון. בשיעור הזה פשוט נספור צעדים, ונראה שאם הרשימה גדלה — מספר הצעדים גם גדל.

יעילות: כמה מעט עבודה (צעדים) אלגוריתם עושה כדי להגיע לאותה תוצאה — פחות צעדים = יעיל יותר.
צעד: פעולה אחת קטנה שהאלגוריתם מבצע, למשל הסתכלות על פריט אחד ברשימה.
גודל הקלט: כמה פריטים יש בקלט — למשל אורך הרשימה. ככל שהוא גדל, בדרך כלל יש יותר צעדים.