כל מה שרצית לדעת על שיטת אכרה-באזזי:
במדעי המחשב, שיטת אכרה-באזזי היא שיטה המשמשת לניתוח ההתנהגות האסימפטוטית של יחס נסיגה (רקורסיה), אשר מופיע באנליזה של אלגוריתמי הפרד ומשול שבהם תתי-הבעיות הן בגדלים שונים בצורה משמעותית.
השיטה מהווה הרחבה משמעותית של שיטת האב, אשר מניחה שתתי-הבעיות של הבעיה הנתונה הן בגדלים זהים.
שיטת אכרה-באזזי תקפה לנוסחאות חוזרות של הצורה: T ( x ) = g ( x ) + ∑ i = 1 k a i T ( b i x + h i ( x ) ) for x ≥ x 0 .
{\displaystyle T(x)=g(x)+\sum _{i=1}^{k}a_{i}T(b_{i}x+h_{i}(x))\qquad {\text{for }}x\geq x_{0}.
} התנאים לשימוש הם:הוכחה לקיום בסיס לאינדוקציה a i {\displaystyle a_{i}} ו- b i {\displaystyle b_{i}} הם קבועים לכל i 0 < b i < 1 {\displaystyle 0<b_{i}<1} לכל i a i > 0 {\displaystyle a_{i}>0} לכל i | g ( x ) | ∈ O ( x c ) {\displaystyle \left|g(x)\right|\in O(x^{c})} כאשר c הוא הקבוע, ו-O הוא סימון אסימפטוטי | h i ( x ) | ∈ O ( x ( log x ) 2 ) {\displaystyle \left|h_{i}(x)\right|\in O\left({\frac {x}{(\log x)^{2}}}\right)} לכל i x 0 {\displaystyle x_{0}} הוא קבועההתנהגות האסימפטוטית של (T(x נמצאת כאשר קובעים את הערך של p כאשר ∑ i = 1 k a i b i p = 1 {\displaystyle \sum _{i=1}^{k}a_{i}b_{i}^{p}=1} ומכניסים את הערך למשוואה: T ( x ) ∈ Θ ( x p ( 1 + ∫ 1 x g ( u ) u p + 1 d u ) ) {\displaystyle T(x)\in \Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}du\right)\right)} באופן אינטואיטיבי, h i ( x ) {\displaystyle h_{i}(x)} מסמלת הפרעה באינדקס של T.
כאשר מסמנים ש- ⌊ b i x ⌋ = b i x + ( ⌊ b i x ⌋ − b i x ) {\displaystyle \lfloor b_{i}x\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)} ו ⌊ b i x ⌋ − b i x {\displaystyle \lfloor b_{i}x\rfloor -b_{i}x} תמיד בין 0 ל-1, h i ( x ) {\displaystyle h_{i}(x)} יכול לשמש כדי להתעלם מפונקציית הערך השלם באינדקס.
בדומה לכך, משוואה דומה יכולה לשמש כדי להתעלם מההפרעה בפונקציית התקרה.
לדוגמה, T ( n ) = n + T ( 1 2 n ) {\displaystyle T(n)=n+T\left({\frac {1}{2}}n\right)} ו- T ( n ) = n + T ( ⌊ 1 2 n ⌋ ) {\displaystyle T(n)=n+T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)} , יהיו בעלי אותה התנהגות אסימפטוטית לפי שיטת אכרה-באזזי.
השיטה קרויה על שם מפתחיה: מוחמד אכרה ולואי באזזי, שניהם מכהנים כמרצים לאלקטרוניקה והנדסת מחשבים באוניברסיטה האמריקנית בביירות.