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

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

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

התנאים לשימוש הם:
 הוכחה לקיום בסיס לאינדוקציה
  ו- הם קבועים לכל i
  לכל i
  לכל i
  כאשר c הוא הקבוע, ו-O הוא סימון אסימפטוטי
  לכל i
  הוא קבוע

ההתנהגות האסימפטוטית של (T(x נמצאת כאשר קובעים את הערך של p כאשר  ומכניסים את הערך למשוואה:

באופן אינטואיטיבי,  מסמלת הפרעה באינדקס של T. כאשר מסמנים ש- ו תמיד בין 0 ל-1,  יכול לשמש כדי להתעלם מפונקציית הערך השלם באינדקס. בדומה לכך, משוואה דומה יכולה לשמש כדי להתעלם מההפרעה בפונקציית התקרה. לדוגמה,  ו-, יהיו בעלי אותה התנהגות אסימפטוטית לפי שיטת אכרה-באזזי.

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

קישורים חיצוניים
 Mohamad Akra, Louay Bazzi, On the solution of linear recurrence equations, Computational Optimization and Applications 10(2):195–210, 1998

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