הצגת המקור של הדף "שיטת אכרה-באזזי"

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

שיטת אכרה-באזזי תקפה לנוסחאות חוזרות של הצורה:
:<math>T(x)=g(x) + \sum_{i=1}^k a_i T(b_i x + h_i(x))\qquad \text{for }x \geq x_0.</math>

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

ההתנהגות האסימפטוטית של (T(x נמצאת כאשר קובעים את הערך של p כאשר <math>\sum_{i=1}^k a_i b_i^p = 1</math> ומכניסים את הערך למשוואה:

:<math>T(x) \in \Theta \left( x^p\left( 1+\int_1^x \frac{g(u)}{u^{p+1}}du \right)\right)</math>

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

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

==קישורים חיצוניים==
* Mohamad Akra, Louay Bazzi{{כ}}, [https://raw.githubusercontent.com/emintham/Papers/master/Akra,Bazzi-%20On%20the%20Solution%20of%20Linear%20Recurrence%20Equations.pdf On the solution of linear recurrence equations], {{כ}}'''Computational Optimization and Applications''' 10(2):195–210, 1998

[[קטגוריה:משפטים במדעי המחשב]]
[[קטגוריה:סיבוכיות חישובית]]