הסבר בזמן (O(n על סימונים אסימפטוטיים

כל מי שמתחיל ללמוד מדעי המחשב נתקל חיש קל בסימון האסימפטוטי \( O\left(n\right) \). המשפט הזה נשמע לכם כמו ג'יבריש מוחלט? מצויין! הפוסט הזה מיועד בעיקר לכם, ובפרט לאלו מכם שהעניין הזה הבהיל אותם מלהתעסק במדעי המחשב. השורה התחתונה היא שזה סימון מתמטי פשוט יחסית, שמטרתו לעשות את החיים קלים לכל העוסקים במלאכה; בואו ננסה להבין למה בכלל צריך לעשות את החיים קלים, ואיך הסימון הזה עושה אותם כאלה.

נתחיל בניתוץ המיתוס הבסיסי. אנשים מגיעים משום מה למסקנה שמתמטיקאים הם אנשים מאוד מדויקים, ושהם אנשים מאוד חרוצים. לא נכון! מתמטיקאים הם עצלנים והם מאוד אוהבים קירובים והזנחות. הם פשוט עושים אותם נכון. בעוד שהפיזיקאי יגיד "הממ... עבור ערכים קרובים לאפס של \( x \) מתקיים ש-\( x \) ו-\( \sin x \) זה בערך אותו דבר" ואז יחליף כל מופע במשוואה של \( \sin x \) ל-\( x \), המתמטיקאי יגיד "הממ, כאשר \( x\to0 \) אז \( \sin x=x+o\left(1\right) \)". המטרה היא לתת למשוואה השניה משמעות מדויקת ופורמלית, למרות שהיא מתארת קירוב והזנחה.

במדעי המחשב קירובים שכאלו הופכים להיות צורך אקוטי למדי. חלק ניכר מהמתמטיקה של מדעי המחשב עוסקת בניתוח זמן הריצה של אלגוריתמים (מהו אלגוריתם? חשבו עליו כעל תוכנית מחשב. מהי תוכנית מחשב? אה...). עכשיו, אפילו אלגוריתמים פשוטים הם עדיין בעייתיים לניתוח מדויק. ראשית כל צריך להגדיר מהו "צעד בסיסי" שהאלגוריתם מבצע, וזה כבר אסון: האם פעולה חשבונית היא צעד בסיסי? אבל אנו יודעים שחיבור לוקח זמן קצר בהרבה מאשר כפל או, חס ושלום, חילוק. אבל מצד שני, במחשבים שבהם מספרים מיוצגים בצורה סטנדרטית, כפל או חלוקה ב-2 הם דווקא קלים מאוד לביצוע על ידי הזזה של ביט בודד; ברמת החומרה אפשר אולי לממש את זה אפילו יותר מהר מאשר חיבור! בנוסף, הזמן שדורשות פעולות בסיסיות עשוי להשתנות ממעבד למעבד; הוא עשוי להיות תלוי בתנאים הפיזיים שבהם המעבד פועל באותו הרגע; והאלגוריתם עצמו עשוי לרוץ על מעבד שמבצע אופטימיזציות מתוחכמות (למשל Brach prediction או Out-of-order execution). בקיצור, כאשר מנתחים את זמן הריצה של אלגוריתמים, מראש ברור לכולם שאנחנו לא יכולים לקבל מספר מדויק אלא רק הערכה; לכן השימוש בקירובים הוא כל כך טבעי.

מכיוון שאין משמעות למספרים מדוייקים, מה שאנחנו רוצים לדעת הוא את ההתנהגות האסימפטוטית של זמן הריצה. מה זה אומר? בדרך כלל אלגוריתם נבנה כך שיהיה מסוגל לעבוד על קלטים מכל גודל שהוא. אז אפשר לדבר על פונקציה \( f\left(n\right) \) שמקבלת את גודל הקלט (גם "גודל הקלט" הוא מושג שנתון לכמה פרשנויות) ומחזירה את זמן הריצה של האלגוריתם על אותו קלט, כאשר זמן הריצה הזה הוא פשוט "מספר הצעדים הבסיסיים" של האלגוריתם (זכרו - "צעד בסיסי" תלוי באלגוריתם עצמו ובמה שאנו מוכנים לקרוא לו צעד בסיסי; ובהחלט ייתכן ששתי פעולות שונות, שלוקחות פרק זמן שונה, עדיין יחשבו שתיהן ל"צעד בסיסי"). לחשב את \( f\left(n\right) \) בצורה מדויקת זה כאב ראש, אבל אפשר להשוות את \( f\left(n\right) \) לפונקציות פשוטות, למשל \( n^{2} \). אם למשל לכל \( n \) טבעי מתקיים \( f\left(n\right)<n^{2} \), אז אנחנו יודעים שזמן הריצה של האלגוריתם שמיוצג על ידי \( f \) הוא לא גדול מדי - הוא לכל היותר ריבועי בגודל הקלט.

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

def find_min_max(list)
  min = max = list[0]
  for k in 1...list.length do
    min = list[k] if min > list[k]
    max = list[k] if max < list[k]
  end
  return [min, max]
end

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

אז מה יש לנו כאן? שתי פעולות אתחול, ועוד \( 2n-2 \) פעולות השוואה (כש-\( n \) הוא הגודל של list) שאם כל אחת מהן מצליחה, יש לנו עוד פעולת השמה. במקרה הגרוע ביותר (שהוא מה שבדרך כלל אנו מתעניינים בו) כל פעולת השוואה "תצליח" ולכן תסתיים בהשמה, כך שיהיו לנו עוד \( 2n-2 \) פעולות השמה (בפועל זה לא יכול לקרות אף פעם - למה?). סך הכל: \( 4n-2 \) פעולות בסיסיות של השוואה והשמה. אז חסם עבור האלגוריתם הוא \( f\left(n\right)<4n \), אבל בשביל מה צריך את ה-4 שם? אין לו חשיבות אסימפטוטית גדולה במיוחד, במובן זה שאפילו \( 100n \) זה עדיין יותר מהיר עבור ערכים גדולים של \( n \) מאשר, נאמר, \( n^{2} \). חוץ מזה, בגלל שהשוואה והשמה לא לוקחות אותו פרק זמן, ה-4 הזה הוא ממילא שקר: אם, למשל, פעולה של השוואה לוקחת פי 2 יותר זמן מפעולה של השמה אז נכון לחשוב על השוואה כשתי פעולות בסיסיות ואז נקבל \( 2n+2\left(2n-2\right)=6n-4 \) פעולות בסיסיות, כלומר חסם של \( f\left(n\right)<6n \) - שינוי בקבוע שבו מוכפל ה-\( n \). לכן אנחנו מעדיפים להשתמש בסימון שממילא לא מתעניין בקבועים הללו ולומר ש-\( f\left(n\right)=O\left(n\right) \).

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

def faster_find_min_max(list)
  min = max = list[0]
  k = (list.length % 2 == 1)?(1):(0)

  while k < list.length
    if (list[k] < list[k+1])
      min_candidate, max_candidate = list[k], list[k+1]
    else
      min_candidate, max_candidate = list[k+1], list[k]
    end
    max = max_candidate if max_candidate > max
    min = min_candidate if min_candidate < min

    k = k + 2
  end

  return [min, max]
end

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

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

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

ראשית כל, צריך להבהיר מה "שדה המשחק" שלנו. אנחנו מדברים על פונקציות \( f:\mathbb{N}\to\mathbb{N} \) שמקבלות מספרים טבעיים ומחזירות מספרים טבעיים. אפשר לדבר על סימונים אסימפטוטיים גם בהקשרים אחרים ואתן דוגמאות לכך, אבל אז נצהיר במפורש על שינוי שדה המשחק. בניתוח סיבוכיות של אלגוריתמים פונקציות מטבעיים לטבעיים הן מה שצץ באופן טבעי, כי אורך קלט ומספר צעדי ריצה הם בדרך כלל מספרים טבעיים (אפשר להתקטנן כאן. בואו לא נעשה את זה).

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

ההגדרה הזו עושה שני דברים: ראשית, היא מתעלמת מקבועים, בכך שהיא מרשה ל-\( g\left(n\right) \) להיות מוכפל בקבוע כלשהו; שנית, היא מתעלמת מערכים קטנים של \( n \) בכך שהיא מרשה לאי השוויון להתקיים רק החל מ-\( n_{0} \) כלשהו. זה אומר שאנחנו מתעניינים רק ב"התנהגות לטווח ארוך" של הפונקציה, מה שכמובן פותח פתח לאנומליות של אלגוריתם א' שטוב יותר אסימפטוטית מאלגוריתם ב', אבל רק עבור קלטים שהגודל שלהם גדול ממספר האטומים ביקום. כן, זה קורה. כן, כל מדעני המחשב מודעים לזה. כן, זה לא מפריע לנו אם אנחנו לא מסיקים מחסמים אסימפטוטיים שכאלו יותר מאשר צריך להסיק מהם.

עד כאן הכל טוב. הבעיה היא שלפעמים רוצים להשתמש בסימון \( O \) גם באגף שמאל של המשוואה, ואז All hell breaks loose. למשל, הביטו במשוואה הבאה:

\( n^{2}+O\left(n\right)=O\left(n^{2}\right) \)

המשוואה רוצה לומר את הדבר הבא - קחו את הפונקציה \( n^{2} \) ותוסיפו לה פונקציה כלשהי \( h\left(n\right) \) שמקיימת \( h\left(n\right)=O\left(n\right) \), והתוצאה הכוללת תהיה \( O\left(n^{2}\right) \). במילים אחרות, משמעותו הפורמלית של השוויון שלמעלה היא "לכל \( h\left(n\right)=O\left(n\right) \) מתקיים \( n^{2}+h\left(n\right)=O\left(n^{2}\right) \)".

טוב ויפה, אבל כדי לראות איך זה מסתבך, שימו לב לכך שאפשר היה להיפטר לגמרי מה-\( n^{2} \) ולהיוותר עם ה"משוואה" הבאה:

\( O\left(n\right)=O\left(n^{2}\right) \)

עכשיו, אנחנו נוהגים לחשוב על שוויון כיחס סימטרי. כלומר, אם \( O\left(n\right)=O\left(n^{2}\right) \) אז היינו מצפים שיתקיים גם \( O\left(n^{2}\right)=O\left(n\right) \). רק שזה לא נכון, כי \( n^{2} \) לא מקיימת \( n^{2}=O\left(n\right) \) (לא קשה להוכיח את זה). מכאן שהשימוש בסימן השוויון כאן הוא בעייתי. לי עצמי אין בעיה גדולה עם ויתור על הסימטריה של השוויון - אני חושב על \( a=b \) בהקשר הזה כאומרת "\( a \) הוא \( b \), אפילו אם לא בהכרח \( b \) הוא \( a \)" אבל לאנשים רבים זה כן מפריע. למי שזה מפריע לו אני יכול להגיד בעיקר - זה סימון. מטרתו לעשות את החיים קלים יותר. הוא מאוד מועיל כשרוצים לעשות שרשרת של שוויונות (מה שקורה כאשר מפשטים באופן הדרגתי ביטוי מסובך כלשהו). חבל לוותר עליו.

בגלל הבעייתיות הזו לפעמים מגדירים את \( O\left(g\left(n\right)\right) \) בתור מחלקת כל הפונקציות שמקיימות את התכונה שסימנתי כ-\( f\left(n\right)=O\left(g\left(n\right)\right) \) (במילים אחרות, \( f\left(n\right)\in O\left(g\left(n\right)\right) \) אם ורק אם קיימים \( c,n_{0} \) כך ש-\( f\left(n\right)<cg\left(n\right) \) לכל \( n>n_{0} \)). עם זאת, בפועל אני לא מכיר מקומות שמשתמשים ב-\( \in \) בהקשר הזה אלא תמיד בסימן השוויון המושמץ. התרגלתי.

נסכם: אפשר להשתמש ב-\( O \) בחופשיות בתוך משוואות, אבל אם הוא מופיע בהן צריך לזכור שהמשוואה אינה סימטרית. למשל, במשוואה \( n+O\left(n^{2}\right)=n^{2}+O\left(n\right) \), מה שצריך להבין הוא שלכל פונקציה \( h\left(n\right)\in O\left(n^{2}\right) \), קיימת פונקציה \( h^{\prime}\left(n\right)\in O\left(n\right) \) כך ש-\( n+h\left(n\right)=n^{2}+h^{\prime}\left(n\right) \). כך זה באופן כללי, גם כשיש יותר מסימון אסימפטוטי אחד בכל אגף - לכל השמה של ערכים מתאימים לסימונים האסימפטוטיים באגף שמאל, קיימת השמה לסימונים באגף ימין כך שיתקיים שוויון.

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

סימונים דומים יש עבור חסמים תחתונים: \( f\left(n\right)=\Omega\left(g\left(n\right)\right) \) אם \( g\left(n\right)=O\left(f\left(n\right)\right) \), ו-\( f\left(n\right)=\omega\left(g\left(n\right)\right) \) אם \( g\left(n\right)=o\left(f\left(n\right)\right) \). הסימון האחרון, \( \Theta \), בא לציין חסם הדוק אסימפטוטית - חסם שהוא גם עליון וגם תחתון בו זמנית. \( f\left(n\right)=\Theta\left(g\left(n\right)\right) \) פירושו ש-\( f\left(n\right)=O\left(g\left(n\right)\right) \) וגם \( f\left(n\right)=\Omega\left(g\left(n\right)\right) \), או באופן מפורש שקיימים קבועים \( c_{1},c_{2} \) ו-\( n_{0} \) כך ש-\( c_{1}\cdot g\left(n\right)\le f\left(n\right)\le c_{2}\cdot g\left(n\right) \) לכל \( n>n_{0} \).

סימון אחד שכדאי להתייחס אליו במפורש הוא הסימון \( f\left(n\right)=O\left(1\right) \). כאשר \( 1 \) בא לציין את הפונקציה הקבועה 1, ומה ש-\( f\left(n\right)=O\left(1\right) \) אומר הוא ש-\( f\left(n\right) \) חסומה על ידי קבוע (קיים \( c \) כך ש-\( f\left(n\right)<c \) לכל \( n \)). בדומה, \( f\left(n\right)=o\left(1\right) \) בא לציין פונקציה ששואפת לאפס כאשר \( n \) שואף לאינסוף - עבור פונקציות מטבעיים לטבעיים זה לא ממש קורה, אבל בהקשרים אחרים זה בהחלט יכול לקרות. בואו נראה דוגמה פשוטה: הפונקציה \( f\left(x\right)=\frac{1}{x} \) מקיימת \( f\left(x\right)=o\left(1\right) \) כאשר \( x \) שואף לאינסוף. כמו כן, \( f\left(x\right)=x \) מקיימת \( f\left(x\right)=o\left(1\right) \) כאשר \( x \) שואף לאפס. כפי שאתם רואים, חשוב שיהיה ידוע ברקע לאן \( x \) שואף.

עכשיו אפשר להבין את הסימון מתחילת הפוסט. משפט ידוע במתמטיקה, שכבר הקדשתי לו פוסט בעבר, הוא שמתקיים \( \lim_{x\to0}\frac{\sin x}{x}=1 \). אפשר לנסח את זה בתור \( \sin x=O\left(x\right) \) עבור \( x \) שואף לאפס. אפשר גם יותר טוב מזה - אנחנו יודעים שטור הטיילור של \( \sin x \) מתחיל כך: \( \sin x=x-\frac{x^{3}}{3!}+\frac{x^{5}}{5!}-\dots \). אפשר לכתוב את זה גם כך: \( \sin x=x+o\left(1\right) \), פשוט כי \( \left(-\frac{x^{3}}{3!}+\frac{x^{5}}{5!}-\dots\right)=o\left(1\right) \) כאשר \( x \) שואף לאפס. למעשה, אפשר גם לכתוב \( \sin x=x+O\left(x^{3}\right) \) וזה יהיה חסם אפילו יותר טוב (זכרו - כשאיקס שואף לאפס, חזקה גדולה יותר של איקס תיתן לנו משהו קטן יותר). זו דוגמה קטנה לאופן שבו הסימון הזה מופיע בחלקי מתמטיקה שאינם מדעי המחשב - כדאי לציין שהוא עתיק הרבה יותר ממדעי המחשב עצמם.

ועכשיו לבחון את עצמכם! האם, אחרי קריאת הפוסט, אתם מבינים מה לכל הרוחות ניסיתי לומר בכותרת שלו? אם כן, סימן שהצלחתי!