מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי - דג הסלמון: הבדלים בין גרסאות בדף

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