מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←דמיון לאופרטורי השוואה: הגהה |
|||
שורה 228:
===הקבוצה <math dir = "ltr">\displaystyle O</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 g(n)</math>. הקביעה <math dir = "ltr">\displaystyle f(n) = O(g(n))</math> אומרת שקצב הגדילה של<math dir = "ltr">\displaystyle f(n)</math> חסום מלמעלה
ראשית, נשים לב שמתקיים <math dir = "ltr">\displaystyle f(n) \le g(n) \Rightarrow f(n) = O(g(n))</math> (למה?).
שורה 238:
===הקבוצה <math dir = "ltr">\displaystyle \Omega</math> והייחס <math dir = "ltr">\displaystyle \ge</math>===
הקביעה <math dir = "ltr">\displaystyle f(n) \ge g(n)</math> אומרת ש<math dir = "ltr">\displaystyle f(n)</math> חסומה מלמעלה על ידי <math dir = "ltr">\displaystyle g(n)</math>. הקביעה <math dir = "ltr">\displaystyle f(n) = \Omega(g(n))</math> אומרת שקצב הגדילה של<math dir = "ltr">\displaystyle f(n)</math> חסום מלמעלה
ראשית, נשים לב שמתקיים <math dir = "ltr">\displaystyle f(n) \ge g(n) \Rightarrow f(n) = \Omega(g(n))</math> (למה?).
שורה 250:
הקביעה <math dir = "ltr">\displaystyle f(n) = g(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 f(n) = g(n) \Rightarrow f(n) = \Theta(g(n))</math> (למה?).
| |||