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

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

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

$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}$ ו-$b_{i}$ הם קבועים לכל i
• $0<b_{i}<1$ לכל i
• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i > 0} לכל i
• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left|g(x)\right| \in O(x^c)} כאשר c הוא הקבוע, ו-O הוא סימון אסימפטוטי
• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| h_i(x) \right| \in O\left(\frac{x}{(\log x)^2}\right)} לכל i
• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0} הוא קבוע

ההתנהגות האסימפטוטית של (T(x נמצאת כאשר קובעים את הערך של p כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^k a_i b_i^p = 1} ומכניסים את הערך למשוואה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(x) \in \Theta \left( x^p\left( 1+\int_1^x \frac{g(u)}{u^{p+1}}du \right)\right)}

באופן אינטואיטיבי, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h_i(x)} מסמלת הפרעה באינדקס של T. כאשר מסמנים ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lfloor b_i x \rfloor = b_i x + (\lfloor b_i x \rfloor - b_i x)} והפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lfloor b_i x \rfloor - b_i x} תמיד בין 0 ל-1, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h_i(x)} יכול לשמש כדי להתעלם מפונקציית הערך השלם באינדקס. בדומה לכך, משוואה דומה יכולה לשמש כדי להתעלם מההפרעה בפונקציית התקרה. לדוגמה, הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle T(n)=n+T\left({\frac {1}{2}}n\right)} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n) = n + T \left(\left\lfloor \frac{1}{2} n \right\rfloor \right)} , יהיו בעלי אותה התנהגות אסימפטוטית לפי שיטת אכרה-באזזי.

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

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

שגיאות פרמטריות בתבנית:מיון ויקיפדיה
שימוש בפרמטרים מיושנים [ דרגה ] שיטת אכרה-באזזי16551707