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

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

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

תוכן עניינים

1 הגדרה פורמלית
2 הכללה
3 דוגמאות
- 3.1 ניתוח סיבוכיות אלגוריתמים
- 3.2 חסם על קירובים
4 לקריאה נוספת

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

השימוש בסימון אסימפטוטי מערב תמיד פונקציה $\ 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)$ . ביטוי זה עשוי לגרום לבלבול אם מתייחסים אליו כבא לציין שוויון ולא שייכות; בפרט, הוא אינו סימטרי. למשל, מתקיים $\ O(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)$ אם ורק אם $\ 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))$	חסם עליון אסימפטוטי	$\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$ - כלומר, השארית זניחה ביחס לאיבר האחרון בטור שמחושב באופן מדויק.