NEW
Font size
Worksheetsיעילות
Total questions: 6
Worksheet time: 12mins
לבעיית הסוכן הנוסע
עדיין לא נמצא אלגוריתם שיכול לחשב את המסלול הקצר ביותר מבין כל המסלולים האפשריים
יש אלגוריתם מסובך מאד, ולכן לא ניתן לביצוע בזמן הגיוני
יש אלגוריתם קצר וברור, אך משך החיפוש כאשר מספר האתרים גדול מ - 14 הוא בלתי סביר
איך מודדים יעילות?
לפני מספר הנתונים שהתוכנית קולטת
לפי מספר פעולות היסוד שעל המחשב לבצע
במילישניות - אלפיות השניה
O(1) זמן ריצה קבוע - יעילות
כאשר המחשב מבצע מקסימום 9 פעולות יסוד
כאשר אין תלות בין מספר פעולות היסוד לבין אורך הקלט
כאשר בכל המחשבים התוכנית תרוץ במשך אותו הזמן
חישוב היעילות בתוכנית הלימודים נעשית על פי
המקרה הגרוע ביותר
המקרה הממוצע
המקרה הטוב ביותר
?מהו שיפור משמעותי יותר באלגוריתם
כאשר האלגוריתם מקצר את זמן הריצה בדקה לכל הפחות
כאשר האלגוריתם משתפר בסדר גודל
כאשר האלגוריתם משתפר בקבוע
O(n) האם אלגוריתם ביעילות
תמיד עדיף על אלגוריתם ביעילות
? O(n2)
רק אם למחשב מעבד מהיר מאד
בקלטים קטנים לפעמים O(n2) עדיף
O(n2) תמיד עדיף
ברור