מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי - דג הסלמון: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 84:
{{משפט|תוכן =
זמן הריצה של {{קוד בשורה|Min-Time(n)}} הוא <math dir = "ltr">\displaystyle \Omega(1.5^n)</math>.
}} {{הוכחה|1 =
זמן הריצה של {{קוד בשורה|Min-Time(n)}} נתון ע"י נוסחת הנסיגה <math dir = "ltr">\displaystyle T(n) = \sum_{i = 1}^{n - 1}[T(i)] +
\Theta(n)</math>.
[[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים#נוסחת נסיגה לבעיית "דג הסלמון"|אפשר להוכיח את החסם התחתון באינדוקציה]].
}}
קצת מפתיע שהפתרון כ"כ איטי, מפני שאם מתבוננים בקוד של {{קוד בשורה|Min-Time}}, אפשר לראות שהוא מבצע מספר ליניארי של פעולות (חוץ מקריאות רקורסיביות). יותר מכך, {{קוד בשורה|Min-Time}} יכול להקרא רק עם <math dir = "ltr">\displaystyle n</math> ארגומנטים שונים. נראה ש'''מספר''' הפעמים שהוא נקרא - הוא זה שגבוה כ"כ. במחשבה נוספת, נתן לראות ש{{קוד בשורה|Min-Time}} נקרא שוב ושוב עם אותם הארגומנטים.
| |||