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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 219:
{{הערה|1 =
ייתכן ש<math dir = "ltr">\displaystyle f(n) = O(g(n))</math>,‏ <math dir = "ltr">\displaystyle f(n) = \Omega(g(n))</math>, או <math dir = "ltr">\displaystyle f(n) = \Theta(g(n))</math>, אך הגבול פשוט '''אינו''' קיים.}}
 
 
 
==דמיון לאופרטורי השוואה==
 
בדף זה ראינו דרכים לסווג פונקציות לפי סדרי הגדילה שלהן. יש דמיון כלשהו בין הקבוצות שראינו לבין אופרטורי השוואה אלגבריים:
 
====הקבוצה <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 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) \Righarrow f(n) = O(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) = O(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) = O(g(n)) \bigwedge g(n) = O(h(n)) \Rightarrow f(n) = O(h(n))</math>
 
 
 
 
==סיכום==
 
 
 
ב[[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/חיפוש לינארי ובינרי|חיפוש לינארי ובינרי]], ראינו דוגמאות ראשונות של ניתוח אלגוריתמים. דף זה עסק בסדרי גדילה של פונקציות.