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

נתונה נוסחת הנסיגה הבאה: $$T(n) = 4T\!\left(\frac{n}{2}\right) + n^2 \log n, \quad T(1) = \Theta(1)$$ **א.** הגדירו את הפרמטרים $a, b, f(n)$ וחשבו את $n^{\log_b a}$. **ב.** בדקו את שלושת המקרים הסטנדרטיים של משפט האב. הסבירו מדוע אף אחד מהם אינו חל ישירות. **ג.** השתמשו ב**גרסה המורחבת** של מקרה 2 (עם גורם לוגריתמי) כדי לקבוע את הסדר האסימפטוטי של $T(n)$.

רמז: חשבו את $n^{\log_b a}$ וגלו שהוא שווה ל-$n^2$ — אותו סדר גודל כמו $f(n)$, **פרט לגורם לוגריתמי**. מסיבה זו שלושת המקרים הסטנדרטיים אינם מספיקים. חפשו את הגרסה המורחבת של מקרה 2: אם $f(n) = \Theta\!\left(n^{\log_b a} \cdot \log^k n\right)$ לאיזה $k$, מה מקבלים?

פתרון: **א. זיהוי הפרמטרים:** $a = 4,\; b = 2,\; f(n) = n^2 \log n$. $$n^{\log_b a} = n^{\log_2 4} = n^2$$ --- **ב. בדיקת המקרים הסטנדרטיים:** - **מקרה 1:** $f(n) = O\!\left(n^{2-\varepsilon}\right)$ לאיזשהו $\varepsilon > 0$? **לא** — $n^2 \log n$ גדל מהר יותר מכל $n^{2-\varepsilon}$. - **מקרה 2 סטנדרטי:** $f(n) = \Theta(n^2)$? **לא** — $n^2 \log n \neq \Theta(n^2)$, שכן $\log n \to \infty$. - **מקרה 3:** $f(n) = \Omega\!\left(n^{2+\varepsilon}\right)$ לאיזשהו $\varepsilon > 0$? **לא** — $n^2 \log n = o\!\left(n^{2+\varepsilon}\right)$ לכל $\varepsilon > 0$. אף מקרה אינו חל — הנסיגה נמצאת ב**פער** שבין מקרה 2 לבין מקרה 3. --- **ג. גרסה מורחבת של מקרה 2:** מציינים ש-$f(n) = n^2 \log n = \Theta\!\left(n^{\log_b a} \cdot \log^k n\right)$ עבור $k = 1$. לפי הגרסה המורחבת של משפט האב: אם $f(n) = \Theta\!\left(n^{\log_b a} \cdot \log^k n\right)$ עבור $k \geq 0$, אז: $$T(n) = \Theta\!\left(n^{\log_b a} \cdot \log^{k+1} n\right)$$ כאן $k = 1$, לכן: $$\boxed{T(n) = \Theta\!\left(n^2 \log^2 n\right)}$$