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