מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי - דג הסלמון: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 189:
כעת נוכיח את המשפט הכללי לפתרון פונקציות בעלות memoization.
{{הוכחה|1=
נצייר שוב את עץ הקריאות הרקורסיביות, אלא שעתה ניקח בחשבון את נושא הmemoization.
שורה 195 ⟵ 197:
חלק מהצמתים מודגשים, וחלק אינם:
#צומת
#צומת אינו מודגש אם הוא מתאר קריאה "פושטית", בה
נשים לב לנקודות הבאות:
#אם צומת לא מודגש, אז אין לו ילדים, ובנוסף, הוא <math dir = "ltr">\displaystyle O(1)</math> (מדוע?)
שורה 202 ⟵ 205:
ננתח כעת בשלבים, לפי הרעיון הבא. בכל שלב:
#ניקח צומת <math dir = "ltr">\displaystyle k</math> מודגש שאין לו ילדים מודגשים.
#ננתח את זמן הריצה שלו, ונרשום את התוצאה בצד. נשים לב שאם לצומת אין ילדים מודגשים, אז כל קריאה רקורסיבית שלו היא אכן <math dir = "ltr">\displaystyle O(1)</math> (מפני שזו איננה ממש קריאה רקורסיבית). זמן הריצה שלו, לכן, הוא אכן <math dir = "ltr">\displaystyle T'(k)</math>.
#נמיר אותו בצומת לא מודגש, מפני שניתחנו כבר את חלק הקוד המסובך בו (ורשמנו אותו בצד). כל שנותר הוא הקריאה לפונקציה, והיא לוקחת <math dir = "ltr">\displaystyle O(1)</math>.
לבסוף נישאר עם צומת יחיד לא מודגש (כלומר בעל זמן ריצה <math dir = "ltr">\displaystyle O(1)</math>, ולכן נקבל שסכום זמני הריצה ששמרנו בצד, הוא בדיוק זמן הריצה של האלגוריתם.
}}
נראה כיצד לעשות זאת בעץ הקודם.
#נתחיל בצומת 1 המודגש. לצומת זה אין כלל ילדים, ולכן במקרה זה <math dir = "ltr">\displaystyle T(1) = T'(1) = O(1)</math>.▼
{{דוגמה|תוכן=
▲
נרשום בצד שעד כה הקריאות שעברנו עליהן עלו <math dir = "ltr">\displaystyle T'(1)</math>, ונחליף את הצומת 1 בצומת לא מודגש. זה מסמן את העובדה שניתחנו כבר את החלק "עם הבשר" בצומת 1, וכל שנותר הוא <math dir = "ltr">\displaystyle O(1)</math>.
[[תמונה:Dsa dynamic programming salmon fish memoized_step_1.png|מרכז|100%|עץ הקריאות הרקורסיביות - שלב 1.]]
נעבור לצומת 2 המודגש. לצומת זה יש ילד לא מודגש יחיד, ולכן במקרה זה זמן הקריאה הוא <math dir = "ltr">\displaystyle T(2)</math> (מפני שהקריאה הרקורסיבית איננה ממש רקורסיבית, אלא קריאה ל"חלק הפושטי" שעולה <math dir = "ltr">\displaystyle O(1)</math>). נוסיף בצד לקריאות שעברנו עליהן את <math dir = "ltr">\displaystyle T'(2)</math>, ונחליף את הצומת 2 בצומת לא מודגש. זה מסמן את העובדה שניתחנו כבר את החלק "עם הבשר" בצומת 2, וכל שנותר הוא <math dir = "ltr">\displaystyle O(1)</math>.
[[תמונה:Dsa dynamic programming salmon fish memoized_step_2.png|מרכז|100%|עץ הקריאות הרקורסיביות - שלב 2.]]
כנ"ל לגבי צומת 3.
[[תמונה:Dsa dynamic programming salmon fish memoized_step_3.png|מרכז|100%|עץ הקריאות הרקורסיביות - שלב 3.]]
נמשיך כך כל הדרך עד <math dir = "ltr">\displaystyle n - 1</math>.
[[תמונה:Dsa dynamic programming salmon fish memoized_step_n_minus_1.png|מרכז|100%|עץ הקריאות הרקורסיביות - שלב n - 1.]]
כשנגיע לצומת <math dir = "ltr">\displaystyle n</math>, כל ילדיו אינם מודגשים, לכן נוכל לעשות עבורו אותו הדבר.
[[תמונה:Dsa dynamic programming salmon fish memoized_step_n.png|מרכז|100%|עץ הקריאות הרקורסיביות - שלב n.]]
}}
{{להשלים}}
| |||