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

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

הגדרה פורמלית

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

הסימון O

דוגמה לסימון O גדול: $f(x)\in O(g(x))$ כי קיים $c>0$ (ובפרט $c=1$) ו-$x_{0}$ (ובפרט $x_{0}=5$) עבורם $\ f(n)\leq \;c\cdot g(n)$ לכל $x\geq x_{0}$.

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

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

מטעמי פשטות, נהוג לכתוב $\ f(n)=O(g(n))$ כאשר הכוונה היא שמתקיים $\ f(n)\in O(g(n))$. ביטוי זה עשוי לגרום לבלבול אם מתייחסים אליו כמציין שוויון ולא שייכות; בפרט, הוא אינו סימטרי. למשל, מתקיים $\ n=O(n^{2})$, אבל $\ O(n^{2})\neq 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)$ אם ורק אם $\ g=O(f)$
• $\ f=\omega (g)$ אם ורק אם $\ g=o(f)$
• $\ f=\Theta (g)$ אם ורק אם $\ f=O(g)$ וגם $\ f=\Omega (g)$

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

סיכום

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

סימון	הגדרה	הגדרה מתמטית
$f(n)\in O(g(n))$	$g(n)$ חסם עליון אסימפטוטי	$\limsup _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|<\infty$
$f(n)\in o(g(n))$	$g(n)$ שולט אסימפטוטית	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0$
$f(n)\in \Omega (g(n))$	$g(n)$ חסם תחתון אסימפטוטי	$\liminf _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|>0$
$f(n)\in \omega (g(n))$	$g(n)$ זניח אסימפטוטית	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=\infty$
$f(n)\in \Theta (g(n))$	$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)$ ופונקציה חיובית $\ \phi (x)$ אומרים ש-$\ f(x)=O(\phi (x))$ כאשר $\ x\to x_{0}$ אם קיימים $\ c>0,\delta >0$ כך שלכל x בסביבה $N_{\delta }(x_{0})$ מתקיים $\ |f(x)|\leq c\cdot \phi (x)$. כמו כן, אומרים ש-$\ f(x)=o(\phi (x))$ כאשר $\ x\to x_{0}$ אם לכל $\epsilon >0$ קיים $\delta >0$ כך שלכל x בסביבה $N_{\delta }(x_{0})$ מתקיים $\ |f(x)|\leq \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\to 0}{\frac {o(x^{2})}{x^{2}}}=0$ - כלומר, השארית זניחה ביחס לאיבר האחרון בטור שמחושב באופן מדויק.

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

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

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

לקריאה נוספת

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

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

• גדי אלכסנדרוביץ', הסבר בזמן (O(n על סימונים אסימפטוטיים, באתר "לא מדויק", 6 ביולי 2012
• סימון אסימפטוטי, באתר MathWorld (באנגלית)   

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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