מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 220:
ייתכן ש<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>, אך הגבול פשוט '''אינו''' קיים.}}
{{משימה|1=
מה ההשלכות של כלל הגבול על פולינומים? בצורה אחרת, אם
<math dir = "ltr">\displaystyle f(n) = a_0 + a_1 \cdot n + \cdots + a_p n^p</math>,
ו
<math dir = "ltr">\displaystyle g(n) = b_0 + b_1 \cdot n + \cdots + b_p n^q</math>,
אז מה קובע את סדר הגדילה בין <math dir = "ltr">\displaystyle f</math> ו<math dir = "ltr">\displaystyle g</math>?
}}
{{מוסתר|פתרון|2=
לפי כלל הגבול, נוכל לקבוע את הדברים הבאים:
#אם <math dir = "ltr">\displaystyle p = q</math>, אז <math dir = "ltr">\displaystyle f(n) = \Theta(g(n))</math>.
#אם <math dir = "ltr">\displaystyle p < q</math>, אז <math dir = "ltr">\displaystyle f(n) = O(g(n))</math>.
#אם <math dir = "ltr">\displaystyle p > q</math>, אז <math dir = "ltr">\displaystyle f(n) = \Omega(g(n))</math>.
}}
==דמיון לאופרטורי השוואה==
| |||