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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 230:
הקביעה <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) = O(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) \RigharrowRightarrow f(n) = O(g(n))</math> (למה?).
 
שנית, נשים לב לעוד קווי דמיון: