מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
ביטול גרסה 55226 של Thedsadude (שיחה) |
|||
שורה 226:
בדף זה ראינו דרכים לסווג פונקציות לפי סדרי הגדילה שלהן. יש דמיון כלשהו בין הקבוצות שראינו לבין אופרטורי השוואה אלגבריים:
====הקבוצה <math dir = "ltr">\displaystyle
הקביעה <math dir = "ltr">\displaystyle f(n)
ראשית, נשים לב שמתקיים <math dir = "ltr">\displaystyle f(n)
שנית, נשים לב לעוד קווי דמיון:
*[[#רפלקסיביות|רפלקסיביות]]: לכל פונקציה <math dir = "ltr">\displaystyle f(n)</math> מתקיים <math dir = "ltr">\displaystyle f(n)
*[[#טרנזיטיביות|טרנזיטיביות]]: לכל <math dir = "ltr">\displaystyle f(n), g(n), h(n)</math> מתקיים <math dir = "ltr">\displaystyle f(n)
▲הקביעה <math dir = "ltr">\displaystyle f(n) = g(n)</math> אומרת ש<math dir = "ltr">\displaystyle f(n)</math> אומרת ש<math dir = "ltr">\displaystyle f(n)</math> שווה ל<math dir = "ltr">\displaystyle g(n)</math>. הקביעה <math dir = "ltr">\displaystyle f(n) = \Theta(g(n))</math> אומרת שקצב הגדילה של<math dir = "ltr">\displaystyle f(n)</math> שווה לקצב הגידול של <math dir = "ltr">\displaystyle g(n)</math>. יש דמיון כלשהו בין שתי הקביעות.
▲ראשית, נשים לב שמתקיים <math dir = "ltr">\displaystyle f(n) = g(n) \Rightarrow f(n) = \Theta(g(n))</math> (למה?).
▲*[[#רפלקסיביות|רפלקסיביות]]: לכל פונקציה <math dir = "ltr">\displaystyle f(n)</math> מתקיים <math dir = "ltr">\displaystyle f(n) = f(n)</math>, ובאותו אופן, מתקיים <math dir = "ltr">\displaystyle f(n) = \Theta(g(n))</math>.
▲*[[#טרנזיטיביות|טרנזיטיביות]]: לכל <math dir = "ltr">\displaystyle f(n), g(n), h(n)</math> מתקיים <math dir = "ltr">\displaystyle f(n) = g(n) \bigwedge g(n) = h(n) \Rightarrow f(n) = h(n)</math> ,ובאותו אופן, <math dir = "ltr">\displaystyle f(n) = \Theta(g(n)) \bigwedge g(n) = \Theta(h(n)) \Rightarrow f(n) = \Theta(h(n))</math>
==סיכום==
|