ebooksgratis.com

See also ebooksgratis.com: no banners, no cookies, totally FREE.

CLASSICISTRANIERI HOME PAGE - YOUTUBE CHANNEL
Privacy Policy Cookie Policy Terms and Conditions
שיטת האב – ויקיפדיה

שיטת האב

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

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

[עריכה] תיאור השיטה

בהינתן נוסחת נסיגה מהצורה:

T(n) = a T\left(\frac{n}{b}\right) + f(n) \;\;\;\; \emph{where} \;\; a \geq 1 , b > 1

ניתן למצוא חסם הדוק אסימפטוטית באחד משלושת המקרים הבאים:

  • מקרה א':
f(n) \in O\left( n^{\log_b a - \varepsilon} \right) \rightarrow T(n) \in \Theta\left( n^{\log_b a} \right) \;\;\;\; \emph{where} \;\; \varepsilon > 0
  • מקרה ב':
f(n) \in \Theta\left( n^{\log_b a} \right) \rightarrow T(n) \in \Theta\left( n^{\log_b a} \log(n)\right)
  • מקרה ג':
f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right), a f\left( \frac{n}{b} \right) \le c f(n) \rightarrow T(n) \in \Theta(f(n))\;\;\;\; \emph{where} \;\; \varepsilon > 0, c<1

השיטה פועלת גם עבור \left\lfloor \frac{n}{b} \right\rfloor\, ו-\left\lceil \frac{n}{b} \right\rceil\,.

ערך זה הוא קצרמר בנושא מחשבים. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.


aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -