מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה: הבדלים בין גרסאות בדף

====הקבוצה <math dir = "ltr">\displaystyle \ThetaO</math> והייחס <math dir = "ltr">\displaystyle= \le</math>====

הקביעה <math dir = "ltr">\displaystyle f(n) =\le 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) = \ThetaO(g(n))</math> אומרת שקצב הגדילה של<math dir = "ltr">\displaystyle f(n)</math> שווהחסום מלמעלה לכל היותר על ידי לקצבקצב הגידול של <math dir = "ltr">\displaystyle g(n)</math>. יש דמיון כלשהו בין שתי הקביעות.

ראשית, נשים לב שמתקיים <math dir = "ltr">\displaystyle f(n) =\le g(n) \Rightarrow f(n) = \ThetaO(g(n))</math> (למה?).

*[[#רפלקסיביות|רפלקסיביות]]: לכל פונקציה <math dir = "ltr">\displaystyle f(n)</math> מתקיים <math dir = "ltr">\displaystyle f(n) =\le f(n)</math>, ובאותו אופן, מתקיים <math dir = "ltr">\displaystyle f(n) = \ThetaO(g(n))</math>.

*[[#טרנזיטיביות|טרנזיטיביות]]: לכל <math dir = "ltr">\displaystyle f(n), g(n), h(n)</math> מתקיים <math dir = "ltr">\displaystyle f(n) =\le g(n) \bigwedge g(n) =\le h(n) \Rightarrow f(n) =\le h(n)</math> ,ובאותו אופן, <math dir = "ltr">\displaystyle f(n) = \ThetaO(g(n)) \bigwedge g(n) = \ThetaO(h(n)) \Rightarrow f(n) = \ThetaO(h(n))</math>