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

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

שיטת אכרה-באזזי תקפה לנוסחאות חוזרות של הצורה:

$T(x)=g(x)+\sum _{i=1}^k{a}_{i}T(b_{i}x+h_i(x))\text{for }x\ge x_0.$

התנאים לשימוש הם:

• הוכחה לקיום בסיס לאינדוקציה
• $a_i$ ו-$b_i$ הם קבועים לכל i
• $0<b_i<1$ לכל i
• $a_i>0$ לכל i
• $|g(x)|\in O(x^c)$ כאשר c הוא הקבוע, ו-O הוא סימון אסימפטוטי
• $|h_i(x)|\in O\left(\frac{x}{(\log x{)}^2}\right)$ לכל i
• $x_0$ הוא קבוע

ההתנהגות האסימפטוטית של (T(x נמצאת כאשר קובעים את הערך של p כאשר $\sum _{i=1}^k{a}_i{b}_i^p=1$ ומכניסים את הערך למשוואה:

$T(x)\in \mathrm{\Theta }\left(x^p(1+{\int }_1^x\frac{g(u)}{u^{p+1}}du)\right)$

באופן אינטואיטיבי, $h_i(x)$ מסמלת הפרעה באינדקס של T. כאשר מסמנים ש-$\lfloor b_{i}x\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)$ ו$\lfloor b_{i}x\rfloor -b_{i}x$ תמיד בין 0 ל-1, $h_i(x)$ יכול לשמש כדי להתעלם מפונקציית הערך השלם באינדקס. בדומה לכך, משוואה דומה יכולה לשמש כדי להתעלם מההפרעה בפונקציית התקרה. לדוגמה, $T(n)=n+T\left(\frac{1}{2}n\right)$ ו-$T(n)=n+T\left(\lfloor \frac{1}{2}n\rfloor \right)$, יהיו בעלי אותה התנהגות אסימפטוטית לפי שיטת אכרה-באזזי.

השיטה קרויה על שם מפתחיה: מוחמד אכרה ולואי באזזי, שניהם מכהנים כמרצים לאלקטרוניקה והנדסת מחשבים באוניברסיטה האמריקנית בביירות.

קישורים חיצוניים

• Mohamad Akra, Louay Bazziתבנית:כ, On the solution of linear recurrence equations, תבנית:כComputational Optimization and Applications 10(2):195–210, 1998