יעילות

לבעיית הסוכן הנוסע

• עדיין לא נמצא אלגוריתם שיכול לחשב את המסלול הקצר ביותר מבין כל המסלולים האפשריים

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

• יש אלגוריתם קצר וברור, אך משך החיפוש כאשר מספר האתרים גדול מ - 14 הוא בלתי סביר

איך מודדים יעילות?

• לפני מספר הנתונים שהתוכנית קולטת

• לפי מספר פעולות היסוד שעל המחשב לבצע

• במילישניות - אלפיות השניה

O(1) זמן ריצה קבוע - יעילות

• כאשר המחשב מבצע מקסימום 9 פעולות יסוד

• כאשר אין תלות בין מספר פעולות היסוד לבין אורך הקלט

• כאשר בכל המחשבים התוכנית תרוץ במשך אותו הזמן

חישוב היעילות בתוכנית הלימודים נעשית על פי

• המקרה הגרוע ביותר

• המקרה הממוצע

• המקרה הטוב ביותר

?מהו שיפור משמעותי יותר באלגוריתם

• כאשר האלגוריתם מקצר את זמן הריצה בדקה לכל הפחות

• כאשר האלגוריתם משתפר בסדר גודל

• כאשר האלגוריתם משתפר בקבוע

• רק אם למחשב מעבד מהיר מאד

• ברור