מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
סימון אסימפטוטי משמש לתיאור התנהגותן של פונקציות שערכיהם הולכים וגדלים. נציג שלושה סימונים.
![{\displaystyle O\ notation}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f35b3db8b58b25813cf854cc3a5dbe55c8dd470d)
[עריכה]
תהי
פונקציה שואפת לאינסוף.
נסמן
אם ורק אם קיימים
-ים לכל
כך שעבור כל
מתקיים ש-
כלומר עבור ערכי
הולכים וגדלים שמקבלת
, היא קטנה יותר מ-
עד כדי כפל בקבוע.
-
תיאור התמונה
-
קיים
![{\displaystyle 1=c>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb7999ac9b4035813b1ae408e082e37d2512ab2d)
ו-
![{\displaystyle x_{0}=m=5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f243ef83a91a7292ce9ad92000ceeab22a9f18c)
עבורם
![{\displaystyle f(x)\leq cg(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3dda153a3ed9f7ea80119dcabe2038b4828db771)
כל זמן ש- <math>
- תהי
ו-
אז נוכל לומר כי
(הצבה
) מפני שעבור כל
בהכרח מתקיים ש-
(*)
- תהי
ו-
אז נוכל לומר כי
(הצבה
) מפני שעבור כל
בהכרח מתקיים ש-![{\displaystyle 6x^{4}-2x^{3}\leq x^{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2b935453fbd0d62b5cbff50fbcbce059b6a52ae)
- תהי
אזי עבור
נוכל לומר כי ![{\displaystyle f=O(g)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/beed823cad3e8b52dcfa798e8097d94b3c3c7541)
- תהי
אם ורק אם
כלומר אם מתקיים ש-
מתפקדת כ-
אז נסמן אותה
.
תהי
ו-
אז נוכל לומר כי
(הצבה
) מפני שעבור כל
בהכרח מתקיים ש-
ולכן
(**)
אם ורק אם
וגם
כלומר ל-
יש
, ולאותו הפונקציה,
מתקיים שיש
שהוא הפונקציה
עצמה,
.
- הוכחנו כי אם מתקיים ש-
ו-
אז
(*) וגם מתקיים ש-
(**) ולכן
.
(נובע מזהות ![{\displaystyle log_{a}n={\frac {log_{2}n}{log_{2}a}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/401fa99ec3902092c0514aa0faa2998c175172b3)
דוגמה להשוואה בין יעילותם של פונקציות
[עריכה]
-
תיאור התמונה
-
תיאור התמונה