שיטת האב

שיטת האב (Master Theorem) היא כלי יסודי במדעי המחשב, המשמש לקביעת זמן הריצה האסימפטוטי של אלגוריתמים רקורסיביים. השיטה מאפשרת פתרון יעיל של נוסחאות נסיגה נפוצות המתארות את זמן הריצה, $T(n)$, כתלות בגודל הקלט $n$. נוסחאות אלו הן לרוב מהצורה $T(n)=aT\left({\frac {n}{b}}\right)+f(n)$, כאשר $a\geq 1$ הוא מספר תת־הבעיות, $b>1$ הוא גורם הקטנת גודל הקלט בכל קריאה רקורסיבית, ו־$f(n)$ מייצג את עלות העבודה ללא הקריאות הרקורסיביות (חלוקה ואיחוד). היתרון המרכזי של שיטת האב טמון ביכולתה לספק חסם אסימפטוטי הדוק (באמצעות סימון $\Theta$) לזמן הריצה הכולל של האלגוריתם במהירות, כמעט ללא צורך בחישובים מורכבים. במקרים מסוימים, בהינתן נוסחת נסיגה לזמן ריצה, ניתן ליישם את השיטה כדי למצוא פתרון מיידי, כיוון שהיא מכסה מגוון רחב של יחסי נסיגה סטנדרטיים הנמצאים בשימוש נפוץ באלגוריתמים של הפרד ומשול. השימוש בשיטת האב חוסך את הצורך בפתרון מלא של נוסחת הנסיגה באמצעות שיטות כמו עץ הרקורסיה או שיטת ההצבה.

תיאור השיטה

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

$T(n)=aT\left({\frac {n}{b}}\right)+f(n)\;\;\;\;where\;\;a\geq 1,b>1$

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

• מקרה א':

$f(n)=O\left(n^{\log _{b}(a)-\varepsilon }\right)\rightarrow T(n)=\Theta \left(n^{\log _{b}a}\right)\;\;\;\;where\;\;\varepsilon >0$

• מקרה ב':

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

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

$f(n)=\Theta \left(n^{\log _{b}a}\cdot \log ^{k}n\right)\rightarrow T(n)=\Theta \left(n^{\log _{b}a}\cdot \log ^{k+1}n\right)\;\;\;where\;\;k\geq 0$

• מקרה ג':

$f(n)=\Omega \left(n^{\log _{b}(a)+\varepsilon }\right),af\left({\frac {n}{b}}\right)\leq cf(n)\rightarrow T(n)=\Theta (f(n))\;\;\;\;where\;\;\varepsilon >0,c<1$

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

דוגמה

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

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

ראו גם

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

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.