מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/חסמים עליונים ותחתונים למספר נוסחאות נסיגה/תשובה

1

$\displaystyle T(n)=\Theta (n^{\log _{2}(3)})$, עפ"י מקרה 1 של משפט המאסטר.

2

נפרוש את הנוסחה: $\displaystyle T(n)=$
$\displaystyle T(n-1)+\log(n)=$
$\displaystyle T(n-2)+\log(n-1)+\log(n)=$
$\displaystyle T(n-3)+\log(n-2)+\log(n-1)+\log(n)=$
$\displaystyle \cdots$
$\displaystyle \sum _{i=1}^{n}[\log(i)]=$
$\displaystyle \Theta (n\cdot \log(n)).$
(את המעבר האחרון ראינו בטורים שימושיים.)

3

נגדיר $\displaystyle \alpha '=1-\alpha$. בלי הגבלת הכלליות, נניח ש$\displaystyle \alpha <\alpha '$. להלן עץ הפרישה המתקבל:

עץ הפרישה.

בעץ זה, לכל אחד מהצמתים המצויירים שני ילדים: אם הצומת מתאים לגודל $\displaystyle n'$, אז הילד השמאלי מתאים ל$\displaystyle \alpha n'$,‏ והימני מתאים ל$\displaystyle \alpha 'n'$,‏. מכאן אפשר לראות שמסלולים שמאליים בעץ קצרים יותר ממסלולים ימניים, כי $\displaystyle \alpha '=1-\alpha$.‏ לא כל הרמות בעץ מלאות, אם כן, מה שמקשה מעט על ניתוח הסיבוכיות. נגדיר כ$\displaystyle h_{min}$ את אורך המסלול השמאלי ביותר, וכ$\displaystyle h_{\max }$ את אורך המסלול הימני ביותר.

קל לראות שכל רמה מלאה בעץ תורמת $\displaystyle \Theta (n)$.‏ הרמה הראשונה תורמת $\displaystyle \Theta (n)$;‏ הרמה השניה תורמת $\displaystyle \Theta (\alpha n)+\Theta (\alpha 'n)=\Theta (n)$,‏ הרמה השלישית תורמת $\displaystyle \Theta (\alpha ^{2}n)+\Theta (\alpha \alpha 'n)+\Theta (\alpha '\alpha n)+\Theta (\alpha '^{2}n)=\Theta (\alpha n)+\Theta (\alpha 'n)\Theta (n)$;‏ וכו'.‏ (אפשר להראות זאת פורמאלית באינדוקציה.)

אפשר לראות, לכן, ש$\displaystyle T(n)$ חסומה מלמטה ע"י $\displaystyle h_{min}\cdot \Theta (n)$, וחסומה מלמעלה ע"י $\displaystyle h_{\max }\cdot \Theta (n)$. אבל היות ש$\displaystyle h_{min}=\Theta (\log(n))$ וכן $\displaystyle h_{\max }=\Theta (\log(n))$, אז $\displaystyle T(n)=\Theta (n\cdot \log(n))$.