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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

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

$ 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
  • $ a_{i}>0 $ לכל i
  • $ \left|g(x)\right|\in O(x^{c}) $ כאשר c הוא הקבוע, ו-O הוא סימון אסימפטוטי
  • $ \left|h_{i}(x)\right|\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 \Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}du\right)\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(\left\lfloor {\frac {1}{2}}n\right\rfloor \right) $, יהיו בעלי אותה התנהגות אסימפטוטית לפי שיטת אכרה-באזזי.

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

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

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


שגיאות פרמטריות בתבנית:מיון ויקיפדיה

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