מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי - דג הסלמון: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 172:
לפני שנוכיח את המשפט הקודם, הבה נראה כיצד להשתמש בו בבעייה שבה עוסק דף זה.
{{משפט|תוכן
זמן הריצה של {{קוד בשורה|Min-Time(n)}} הוא <math dir = "ltr">\displaystyle \Theta(n^2)</math>.}}
{{הוכחה|תוכן
מהתבוננות בקוד, אם כל קריאה רקורסיבית היא <math dir = "ltr">\displaystyle
<math dir = "ltr">\displaystyle T'(k) = \Theta(k)</math>.
לכן, במקרה זה.
}}
כעת נוכיח את המשפט הכללי לפתרון פונקציות בעלות memoization.
[[תמונה:Dsa dynamic programming salmon fish simple recurrence.png|מרכז|100%|עץ הקריאות הרקורסיביות.]]
| |||