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

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

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

### הסימון O
250px|ממוזער|דוגמה לסימון O גדול: <math>f(x) \in O(g(x))</math> כי קיים <math>c>0</math> (ובפרט <math>c=1</math>) ו-<math>x_0</math> (ובפרט <math>x_0 = 5</math>) עבורם <math>\ f(n)\le \;c\cdot g(n)</math> לכל <math> x \geq x_0</math>.

הסימון הנפוץ ביותר הוא הסימון "O" (קרי: אוֹוּ גדול). כאשר עוסקים בשאיפה של \ g(n) לאינסוף, מוגדרת הקבוצה \ O(g(n)) בתור אוסף  כל הפונקציות \ f(n) (בעלות אותו תחום וטווח כמו \ g) עבורן קיימים קבועים חיוביים \ n_0 \in \mathbb{N},0 כך שלכל \ n>n_0 מתקיים \ f(n)\le \;c\cdot g(n). כלומר: עבור ערכי n הולכים וגדלים שמקבלת \ f, היא קטנה יותר מ-\ g עד כדי כפל בקבוע.

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

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

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

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

### סימונים נוספים
f=\Omega(g) \equiv \exists 0

f=\omega(g) \equiv \forall 0

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

* \ f=\Theta(g) אם ורק אם \ f=O(g) וגם \ f=\Omega(g), אולם לעיתים מגדירים כי f=\Theta(g) אם ורק אם \exists c_1, c_2>0, \exists n_0 \in \mathbb{N} \; s.t \; \forall n_0 \le n \; c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) , ולא באמצעות התנאי לעיל, למרות השקילות.

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

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

לדוגמה, עבור פונקציה ממשיות \ f(x) ופונקציה חיובית \ \phi(x) אומרים ש-\ f(x)=O(\phi(x)) כאשר \ x\to x_0 אם קיימים \ c>0,\delta>0 כך שלכל x בסביבה N_\delta(x_0) מתקיים \ |f(x)| \le c \cdot\phi(x). כמו כן, אומרים ש-\ f(x)=o(\phi(x)) כאשר \ x\to x_0 אם לכל \epsilon>0 קיים \delta>0 כך שלכל x בסביבה N_\delta(x_0) מתקיים \ |f(x)|\le\epsilon\cdot\phi(x).התנאי האחרון שקול לדרישה \ \lim_{x\to x_0}\frac{f(x)}{\phi(x)}=0. באופן דומה \ f(x)=o(\phi(x)) כאשר \ x\to \infty אם ורק אם \ \lim_{x\to \infty}\frac{f(x)}{\phi(x)}=0.

## שימושים

### ניתוח סיבוכיות אלגוריתמים
נניח כי אלגוריתם מיון מסוים מבצע בדיוק \ 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 - בנוסחה: \lim_{x\to0}\frac{o(x^2)}{x^2}=0 - כלומר, השארית זניחה ביחס לאיבר האחרון בטור שמחושב באופן מדויק.

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

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

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

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

## קישורים חיצוניים
* 
* 

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