סימון אסימפטוטי

סימון אסימפטוטי (גם: סימון לנדאו) הוא קיצור במתמטיקה לתיאור אופן הגדילה של פונקציות כשהקלט נהיה גדול או קטן. המטרה היא להשוות פונקציות אחת לשנייה כדי להבין מי גדל מהר יותר בלי לחשב בדיוק את הערכים.

העיקר הוא פונקציה g שמשמשת כקנה מידה להשוואה. בדרך כלל עובדים עם פונקציות שמקבלות מספרים טבעיים ומחזירות מספרים חיוביים. נדרשת ש-g תהיה אי־שלילית החל ממקום מסוים.

הסימון הגדול O מציין כי פונקציה f אינה גדלה מהר יותר מ‑g עד כדי מכפלה בקבוע. פורמלית יש קבועים כך שלכל n גדל מספיק מתקיים f(n) ≤ c·g(n). מקובל גם לכתוב f(n)=O(g(n)) כקיצור, למרות שזה ביטוי של שייכות ולא שוויון. באופן שווה ניתן להגדיר זאת בעזרת הגבול של היחס f/g.

הסימון הקטן o מציין ש‑f זניחה לעומת g. כלומר קצב הגדילה של f קטן ממש ביחס ל‑g. פורמלית היחס f(n)/g(n) שואף ל־0 כאשר n שואף לאינסוף.

• f = Ω(g): f גדל לפחות בקצב של g (גבול תחתון).
• f = ω(g): f גדל הרבה יותר מ‑g (גבוה בהרבה).
• f = Θ(g): f ו‑g גדלים באותו סדר גודל אסימפטוטי.

הסימונים ניתנים להכללה גם למצבים אחרים מלבד n→∞. למשל עבור פונקציות ממשיות ניתן להגדיר O ו‑o כאשר x שואף לערך מסוים x0 בעזרת גבולות ותנאי סביבה (נקודות קרובות ל‑x0).

במדעי המחשב משתמשים בסימונים כדי לתאר סיבוכיות זמן וזיכרון של אלגוריתמים. לדוגמה, אלגוריתם שמבצע 4n²−2n+1 פעולות נחשב בעל קצב גידול של סדר n², כי עבור n גדולים החלק n² שולט והשאר זניח. גם המקדם (כמו 4) אינו משנה את סדר הגדילה כשהשוואה היא לאיבר חזק יותר כמו n³.

באנליזה משתמשים בסימונים כדי לתאר שגיאה בקירובים. לדוגמה, בפיתוח טיילור של e^x סביב 0, אפשר לכתוב את e^x כאוסף של 1 + x + x²/2 ועוד שארית ששייכת למחלקה o(x²). זה אומר שהשארית זניחה יחסית ל‑x² כאשר x שואף ל‑0.

סימון אסימפטוטי מסביר איך פונקציות מתנהגות כשמספרים גדלים מאוד. זה עוזר להשוות מי גדל מהר יותר.

יש פונקציה שמשרתת כמדד להשוואה. בדוגמאות לרוב מדובר במספרים טבעיים וחיוביים.

O אומר שפונקציה f לא תגדל מהר יותר מהמדרג g, אפילו אם נכפיל את g במספר קבוע. זה עוזר להתמקד בחלק הגדול ביותר בפונקציה.

o אומר ש‑f הרבה יותר קטנה מ‑g. היחס בינהן שואף ל־0 כשהקלט גדל.

• Ω אומר ש‑f לפחות לא קטנה יותר מ‑g.
• ω אומר ש‑f גדלה הרבה יותר מ‑g.
• Θ אומר ששתיהן גדלות בקצב דומה.

ניתן להשתמש בסימונים גם כשמספרים מתקרבים לערך מסוים, לא רק כשנכנסים לאינסוף.

במחשבים נהוג להשתמש בסימונים כדי להשוות אלגוריתמים. למשל בביטוי שיש בו חלק עם n בריבוע וחלקים קטנים יותר, החלק עם n בריבוע שולט כשn גדול.

כשקרובים פונקציות כמו e^x בעזרת פולינום, נשארת שארית קטנה. השארית הזאת נחשבת זניחה לעומת החלק האחרון בפולינום כשה‑x קרוב ל‑0.