מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי - דג הסלמון: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←הדפסת העצירות: תקלדה |
|||
שורה 198:
#צומת מודגש אם הוא מתאר קריאה בה לא רק חלק הmemoization מתבצע, אלא גם החלק העיקרי (שורות 1-2 ב{{קוד בשורה|Min-Time}}).
נשים לב לנקודות הבאות:
#אם צומת לא מודגש, אז אין לו ילדים, ובנוסף, הוא <math dir = "ltr">\displaystyle O(1)</math> (מדוע?)
#כל צומת מופיע מודגש פעם אחת (מדוע?)
ננתח כעת בשלבים, לפי הרעיון הבא. בכל שלב:
#ניקח צומת מודגש שאין לו ילדים מודגשים
#ננתח את זמן הריצה שלו, ונרשום את התוצאה בצד
#נמיר אותו בצומת לא מודגש (שהרי את זמן הריצה שלו שמרנו בצד)
לבסוף נקבל שסכום זמני הריצה ששמרנו בצד, הוא בדיוק זמן הריצה של האלגוריתם.
==הדפסת העצירות==
| |||