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

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

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

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

הסימון O

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

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

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

מטעמי פשטות, נהוג לכתוב $f(n)=O(g(n))$ כאשר הכוונה היא שמתקיים $f(n)\in 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)<c\cdot g(n)$. בסימון באמצעות גבולות ניתן לתאר תכונה זו על ידי הגבול $\underset{n\to \mathrm{\infty }}{\lim }\frac{f(n)}{g(n)}=0$.

סימונים נוספים

$f=\mathrm{\Omega }(g)\equiv \mathrm{\exists }0<c\in \mathbb{ℝ},\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}s.t\mathrm{\forall }{n}_0<n\in \mathbb{\mathbb{N}}c\cdot g(n)\le f(n)$

$f=\omega (g)\equiv \mathrm{\forall }0<c\in \mathbb{ℝ},\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}s.t\mathrm{\forall }{n}_0<n\in \mathbb{\mathbb{N}}c\cdot g(n)<f(n)$

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

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

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

סיכום

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

סימון	הגדרה	הגדרה מתמטית
$f(n)\in O(g(n))$	$g(n)$ חסם עליון אסימפטוטי	$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\left|\frac{f(n)}{g(n)}\right|<\mathrm{\infty }$
$f(n)\in o(g(n))$	$g(n)$ שולט אסימפטוטית	$\underset{n\to \mathrm{\infty }}{\lim }\frac{f(n)}{g(n)}=0$
$f(n)\in \mathrm{\Omega }(g(n))$	$g(n)$ חסם תחתון אסימפטוטי	$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\left|\frac{f(n)}{g(n)}\right|>0$
$f(n)\in \omega (g(n))$	$g(n)$ זניח אסימפטוטית	$\underset{n\to \mathrm{\infty }}{\lim }\frac{f(n)}{g(n)}=\mathrm{\infty }$
$f(n)\in \mathrm{\Theta }(g(n))$	$g(n)$ חסם הדוק אסימפטוטית	$0<\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\left|\frac{f(n)}{g(n)}\right|\le \underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\left|\frac{f(n)}{g(n)}\right|<\mathrm{\infty }$

כאשר הכוונה בכך שגבול כלשהו קטן מאינסוף היא שהגבול הוא מספר ממשי.

הכללה

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

לדוגמה, עבור פונקציה ממשיות $f(x)$ ופונקציה חיובית $\varphi (x)$ אומרים ש-$f(x)=O(\varphi (x))$ כאשר $x\to x_0$ אם קיימים $c>0,\delta >0$ כך שלכל x בסביבה $N_{\delta }(x_0)$ מתקיים $|f(x)|\le c\cdot \varphi (x)$. כמו כן, אומרים ש-$f(x)=o(\varphi (x))$ כאשר $x\to x_0$ אם לכל $ϵ>0$ קיים $\delta >0$ כך שלכל x בסביבה $N_{\delta }(x_0)$ מתקיים $|f(x)|\le ϵ\cdot \varphi (x)$.התנאי האחרון שקול לדרישה $\underset{x\to x_0}{\lim }\frac{f(x)}{\varphi (x)}=0$. באופן דומה $f(x)=o(\varphi (x))$ כאשר $x\to \mathrm{\infty }$ אם ורק אם $\underset{x\to \mathrm{\infty }}{\lim }\frac{f(x)}{\varphi (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$ - בנוסחה: $\underset{x\to 0}{\lim }\frac{o(x^2)}{x^2}=0$ - כלומר, השארית זניחה ביחס לאיבר האחרון בטור שמחושב באופן מדויק.

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

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

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

לקריאה נוספת

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

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

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