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