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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

הגדרה פורמלית[עריכת קוד מקור | עריכה]

השימוש בסימון אסימפטוטי מערב תמיד פונקציה \ g, על פי רוב מקבוצת הטבעיים לעצמה או הממשיים לעצמה. הפונקציה \ g משמשת בתור קנה המידה ההשוואתי לפונקציות אחרות. לרוב ההתעניינות היא בקצב הגדילה של \ g כאשר הערכים שהיא מקבלת שואפים לאינסוף, אולם הדבר אינו הכרחי. בהגדרות שנביא כאן נניח כי כל הפונקציות הן מהטבעיים לעצמם (מצב נפוץ במיוחד במדעי המחשב, מכיוון שמדדי סיבוכיות זמן וזיכרון הם חיוביים ובדידים).

הסימון O[עריכת קוד מקור | עריכה]

הסימון הנפוץ ביותר הוא הסימון "O" (קרי: או גדול). כאשר עוסקים בשאיפה של \ g(n) לאינסוף, מוגדרת הקבוצה \ O(g) בתור אוסף כל הפונקציות \ f(n) (בעלות אותו תחום וטווח כמו \ g) עבורן קיימים קבועים חיוביים \ n_0,c כך שלכל \ n>n_0 מתקיים \ f(n)<c\cdot g(n). כלומר: עבור ערכים הולכים וגדלים שמקבלת \ f, היא קטנה יותר מ-\ g עד כדי כפל בקבוע.

בסימון מתמטי המשתמש בגבולות, ניתן להגדיר כי פונקציה \ f שייכת ל-\ O(g) אם \ \limsup_{n\to\infty}\frac{f(n)}{g(n)}<\infty. שתי ההגדרות שקולות.

מטעמי פשטות, נהוג לכתוב \ f(n)=O(g) כאשר הכוונה היא שמתקיים \ f(n)\isin O(g). ביטוי זה עשוי לגרום לבלבול אם מתייחסים אליו כמציין שוויון ולא שייכות; בפרט, הוא אינו סימטרי. למשל, מתקיים \ n=O(n^2), אבל \ O(n^2)\ne O(n).

הסימון o[עריכת קוד מקור | עריכה]

בעוד הסימון O מציין כי הפונקציה \ f חסומה בקצב גידולה על ידי קצב הגידול של \ g, הרי שהסימון "o" (קרי: או קטן) בא לציין כי קצב הגידול של \ f קטן ממש יחסית לקצב הגידול של \ g.

בצורה פורמלית, אומרים ש-\ f(n) היא \ o(g) אם לכל קבוע \ c קיים \ n_0 כך שלכל \ n>n_0 מתקיים \ f(n)<c\cdot g(n). בסימון באמצעות גבולות ניתן לתאר תכונה זו על ידי הגבול \ \lim_{n\to\infty}\frac{f(n)}{g(n)}=0.

סימונים נוספים[עריכת קוד מקור | עריכה]

באמצעות שני הסימונים שהוגדרו לעיל נהוג להגדיר שלושה סימונים נוספים:

פירוש הסימון \ f=\Omega(g) הוא ש-\ f גדל לפחות בקצב של \ g. פירוש הסימון \ f=\omega(g) הוא ש-\ f גדל בקצב שגדול ממש מהקצב של \ g, ופירוש הסימון \ f=\Theta(g) הוא שקצבי הגידול של \ f ו-\ g הם שווים אסימפטוטית (כלומר, שתי הפונקציות הן מאותו סדר גודל).

סיכום[עריכת קוד מקור | עריכה]

סיכום חמשת הסימונים האסימפטוטיים המקובלים מוצג בטבלה הבאה:

סימון הגדרה הגדרה מתמטית
f(n) \in O(g(n)) חסם עליון אסימפטוטי \limsup_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| < \infty
f(n) \in o(g(n)) זניח אסימפטוטית \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0
f(n) \in \Omega(g(n)) חסם תחתון אסימפטוטי \liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| > 0
f(n) \in \omega(g(n)) שולט אסימפטוטית \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty
f(n) \in \Theta(g(n)) חסם הדוק אסימפטוטית 0 < \liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| \leq \limsup_{n \to \infty} \left|\frac{f(n)}{g(n)}\right|< \infty

הכללה[עריכת קוד מקור | עריכה]

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

לדוגמה, אם עבור הפונקציות הממשיות החיוביות \ f(x),g(x) משתמשים בסימון \ f(x)=o(g(x)) כאשר \ x\to 0, הכוונה היא שמתקיים \ \lim_{x\to 0}\frac{f(x)}{g(x)}=0. כלומר, ההבדל המרכזי הוא בכך ש-\ x שואף בדוגמה זו לאפס, לא לאינסוף.

דוגמאות[עריכת קוד מקור | עריכה]

ניתוח סיבוכיות אלגוריתמים[עריכת קוד מקור | עריכה]

נניח כי אלגוריתם מיון מסוים מבצע בדיוק \ 4n^2-2n+1 פעולות בסיסיות על קלט מגודל \ n. ככל ש-\ n גדל כך ההשפעה של הגורם \ n^2 גדלה בעוד ההשפעה של שאר הגורמים הופכת לזניחה. לדוגמה, עבור \ n=500, גודלו של \ 4n^2 גדול פי 1,000 מגודלו של \ 2n, ופי מיליון מגודלו של \ 1, ולכן שני הגורמים הללו זניחים ביחס ל-\ 4n^2 ובמרבית השימושים לא תהיה להם כל חשיבות.

בנוסף, למקדם \ 4 של הביטוי \ 4n^2 יש חשיבות אפסית בלבד כאשר משווים את הביטוי לביטויים גדולים יותר. למשל, אם משווים את \ 4n^2 ל-\ n^3, כבר עבור \ n=5 הביטוי \ n^3 יהיה גדול יותר. אפילו אם המקדם של \ n^2 יהיה 1,000,000, עבור \ n=1,000,000 ומעלה שוב יתקבל כי \ n^3 גדול יותר. על כן, כאשר מתעניינים בגידול האסימפטוטי של \ n^2 אין חשיבות למקדם שלו.

בשל כך משתמשים בסימון \ 4n^2-2n+1=O(n^2) על מנת לייצג את המאפיין העיקרי של קצב הגידול של הביטוי שבאגף שמאל.

חסם על קירובים[עריכת קוד מקור | עריכה]

ידוע כי ניתן לתאר את פונקציית האקספוננט \ e^x באמצעות טור טיילור אינסופי באופן הבא:

  • \ e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\dots

דרך פשוטה לתאר ביטוי זה כאשר \ x\to 0 באמצעות חסם אסימפטוטי היא זו:

  • \ e^x=1+x+\frac{x^2}{2}+o(x^2)

פירושו של סימון זה הוא כי ניתן לתאר את \ e^x באמצעות הפונקציה \ 1+x+\frac{x^2}{2} ועוד פונקציית "שארית" ששייכת למחלקה \ o(x^2), כלומר היא זניחה יחסית ל-\ x^2 כאשר \ x\to 0 - כלומר, השארית זניחה ביחס לאיבר האחרון בטור שמחושב באופן מדויק.

במקרה זה נכונה גם טענה חזקה יותר:

  • \ e^x=1+x+\frac{x^2}{2}+O(x^3)

כאשר כאן השתמשנו ב-O גדול.

לקריאה נוספת[עריכת קוד מקור | עריכה]