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

נתונה נוסחת הנסיגה הבאה ($a>0$ **פרמטר שלם**): $$T(n)=a\cdot T(\sqrt{n})+\lg^2 n$$ פתרו אותה בשיטת **החלפת המשתנים**, בתלות ב-$a$: **א.** הציבו $m=\lg n$ וכתבו נסיגה ל-$S(m)=T(2^m)$. **ב.** פתרו את $S$ בשלושה מקרים: $a>4$, $a=4$, $a<4$. **ג.** חזרו לביטוי עבור $T(n)$ בכל מקרה.

רמז: הציבו $m=\lg n$: $T(\sqrt{n})=S(m/2)$, קבלים $S(m)=a\cdot S(m/2)+m^2$. ב-$S$: $b=2$, $m^{\log_2 a}=m^{\lg a}$. השוו את $\lg a$ ל-$2$ (מעריך $f$).

פתרון: **א. החלפת משתנים** ($m=\lg n$, $S(m)=T(2^m)$): $$S(m)=a\cdot S\!\left(\frac{m}{2}\right)+m^2$$ **ב. משפט האב על $S$:** $b=2$, $f(m)=m^2$, $m^{\log_2 a}=m^{\lg a}$. **1) $a>4$ ($\lg a>2$):** $f(m)=O(m^{\lg a-\varepsilon})$ → מקרה 1 → $S(m)=\Theta(m^{\lg a})$. **2) $a=4$ ($\lg a=2$):** $f(m)=\Theta(m^2)$ → מקרה 2 → $S(m)=\Theta(m^2\lg m)$. **3) $a<4$ ($\lg a<2$):** רגולריות: $a(m/2)^2=(a/4)m^2\leq c\cdot m^2$ עבור $c=a/4<1$ ✓ → מקרה 3 → $S(m)=\Theta(m^2)$. **ג. חזרה ל-$T(n)$** ($m=\lg n$): $$T(n)=\begin{cases}\Theta((\lg n)^{\lg a})=\Theta(a^{\lg\lg n}) & a>4 \\ \Theta(\lg^2 n\cdot\lg\lg n) & a=4 \\ \Theta(\lg^2 n) & a<4\end{cases}$$