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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
אין תקציר עריכה
אין תקציר עריכה
שורה 126:
{{הוכחה|1=
מהתבוננות בקוד, אם כל קריאה רקורסיבית היא <math dir = "ltr">\displaystyle O(1)</math>, אז נקבל <math dir = "ltr">\displaystyle T'(k) = \Theta(k)</math>. לכן, במקרה זה
<math dir = "ltr">\displaystyle \sum _{ik = 1}^n [\Theta(k)] =
\Theta\left(\sum _{ik = 1}^n [k]\right)
=\Theta(n^2)</math>.
}}