שיטת האב

במדעי המחשב, שיטת האב (Master Theorem) משמשת לפתרון נוסחאות נסיגה של זמן ריצה/זיכרון של אלגוריתמים. כלומר, בהינתן נוסחת נסיגה לזמן ריצתו של אלגוריתם, ניתן להשתמש במקרים מסוימים בשיטה כדי למצוא חסם אסימפטוטי הדוק לזמן הריצה של האלגוריתם כולו. יתרון השיטה בכך שהיא ניתנת ליישום במגוון רחב של מקרים ומספקת פתרון מיידי, כמעט ללא חישוב.

תיאור השיטה

בהינתן נוסחת נסיגה מהצורה:

$T(n)=aT\left(\frac{n}{b}\right)+f(n)wherea\ge 1,b>1$

ניתן למצוא חסם הדוק אסימפטוטית באחד משלושת המקרים הבאים:

• מקרה א':

$f(n)=O\left(n^{{\log }_b(a)-\epsilon }\right)\to T(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)where\epsilon >0$

• מקרה ב':

$f(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)\to T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\log (n))$

• מקרה ב'- מורחב:

$f(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\cdot {\log }^{k}n)\to T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\cdot {\log }^{k+1}n)wherek\ge 0$

• מקרה ג':

$f(n)=\mathrm{\Omega }\left(n^{{\log }_b(a)+\epsilon }\right),af\left(\frac{n}{b}\right)\le cf(n)\to T(n)=\mathrm{\Theta }(f(n))where\epsilon >0,c<1$

השיטה פועלת גם עבור $\lfloor \frac{n}{b}\rfloor$ ו-$\lceil \frac{n}{b}\rceil$.

דוגמה

לדוגמה, בהינתן נוסחת הנסיגה $T\left(n\right)=4T\left(\frac{n}{2}\right)+n^2$, ניתן להשתמש בשיטת האב באופן הבא:

מציבים $a=4,b=2,f(n)=n^2$, ומקבלים: $n^{lo{g}_{b}a}=n^{lo{g}_{2}4}=n^2=f(n)$. זהו מקרה ב' בשיטת האב, ולכן: $T(n)=\mathrm{\Theta }(n^{2}log(n))$.

ראו גם

• שיטת אכרה-באזזי