הבנה בסיסית בהערכת סיבוכיות

תגיות:

מכל החומרים שראיתי וקראתי עד עכשיו, הבנתי שאם נאמר הסיבוכיות של פונקציה היא O5n אז היא נחשבת ל- On, כי מתעלמים לחלוטין מהמכפלות, כמו מכל מספר פעולות קבוע.
למרות זאת, ישנה סיבוכיות המוגדרת O n log n. להבנתי, log n קטן מ- n, מאחר והוא מייצג שבריר שלו. למרות זאת, הסיבוכיות O n log n, להבנתי (שוב), היא מכפלה של של n בלוג n.
אז אם כל מה שרשמתי עליו ‘להבנתי’ הוא נכון, והבנתי נכון, אז נשאלת השאלה: מדוע מכפלה של לדוגמה 5 של n מבוטלת אוטומטית, אך בכל זאת לא מבטלים מכפלה של n בשבריר ממנו…?
אז או שמשהו בסיסי בהגדרות לא הבנתי נכון, או שאין בזה ממש הגיון מובהק… למישהו הסברים?

שאלה טובה, אני לא כזה מבין גדול אבל יכול לשער כי:

5logn - אומר שעבור כל n הפונקציה תעשה את logn 5 פעמים.
5 הוא מספר קבוע ולכן אנו יכולים לדעת בוודאות שהפונקציה תרוץ כל פעם 5 פעמים logn בלי תלות בגודל ה n

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

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

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

זה נכון שמחפשים קצב צמיחה. ואם הפרמטר הגדול ב- n log n הוא n, אז בהמשך לכל ‘הכללים’ של חישוב סיבוכיות, לא ברור לי למה במצב כזה log n רלוונטי, כשהוא מהווה שבריר של n

כי גם logn הוא לא log5 למשל…
הביטוי מתאר את התלות של הפונקציה ב n.
במספרים גדולים - הבדלים האלו נהיים גדולים.

אז נראה שלא ממש הבנו לעומק את ההגדרות, לפחות על פי ההסבר פה:

ובקיצור, ב- On log n, לוג n הוא אינו מכפלה של n, אלא גם הוא שבריר של n, בדומה ל- logn, רק שהבסיס שלו שונה, והוא גדול יותר

ה logn אף פעם לא היה מכפלה של n , ה n בהתחלה הוא מכפלה של כל הביטוי logn …
אם לא אז אולי גם אני לא הבנתי.

לא בטוחה שאני מבינה את הבלבול, אבל מקווה שאני עונה על התהייה.

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

בעולם האמיתי, שבו גם הביצועים חשובים, ינסו להתחשב גם בקבוע ולהוריד אותו כמה שיותר. יש הבדל בין זמן ריצה של קוד הדורש 5n פעולות לזמן ריצה של קוד הדורש 1,000,000,000n פעולות.
אבל, כאשר אנחנו מסתכלים על O אנו מנסים רק להבין כיצד זמן הריצה של הקוד יושפע משינוי בגודל הקלט, המיוצג לרוב ע"י n.
קוד המבצע 5 פעולות על כל איבר ברשימה הניתנת לו יעשה זאת בין אם מספר האיברים ברשימה הוא מאה, אלף או מיליארד. לכן, הכפלת מספר האיברים ברשימה פי 100 תוביל לזמן ריצה ארוך פי 100.
לעומתו, קוד המבצע logn פעולות על כל איבר ברשימה הניתנת לו ישנה גם את מספר הפעולות לכל איבר כאשר גודל הרשימה הניתנת לו ישתנה. כאשר הרשימה הניתנת תהיה בגודל 1,000 הוא יבצע 1,000log(1,000) פעולות, שהן log(1,000) פעולות לאיבר, ואילו כשגודל הרשימה הניתנת לו תהיה בגודל 1,000,000,000 הוא יבצע 1,000,000,000log(1,000,000,000), שהן log(1,000,000,000) פעולות לאיבר. כלומר, זמן הריצה לא יגדל רק פי גודל הרשימה אלא יותר מכך.

3 לייקים

בואו נתחיל רגע בלהבין מה אנחנו רוצים למדוד.

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

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


התשובה לשאלה המקורית ששאלת:

בביטוי 5 \cdot n, זונחים את 5 כי הוא מקדם של n.

למעשה, יש שני סוגים של “חלקים בביטוי” שאנחנו זונחים:

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

מה נחשב “איבר”? כל דבר ש"דבוק" אחד לשני בעזרת כפל, חזקה, חילוק וכדומה. בין שני איברים יהיה פלוס או מינוס. בביטוי n^2 - n + 6 לדוגמה, יש לנו 3 איברים. ניקח רק את n^2, כי הוא עולה בקצב הגבוה ביותר.

למה זונחים איברים שביניהם חיבור/חיסור אבל עולים בקצב נמוך יותר? כי חיבור של איבר שקטן בסדר גודל כמעט לא משפיע על התוצאה הסופית והוא כמעט לא מעניין.
ההבדל בין O(n) לבין O(n^2) הוא אסטרונומי כש־ N=1,000,000 – זה יכול להיות ההבדל בין אלגוריתם שיסיים לרוץ בפחות משנייה לבין כזה שיסיים לרוץ בעוד שבוע.
אבל ההבדל בין O(n^2) לבין O(n^2 + n) במקרה הזה הוא כמעט בלתי נראה – ולכן מרגישים בנוח להשמיט את n – כי מה שמחפשים הוא סדר גודל, ולא חישוב מדויק.


לגבי מקדמים, אני אנסה לתת gut feeling סביר:

  1. בסופו של דבר, מהירות של תוכנה נגזרת מכמות הפעולות שהמעבד מריץ [קצת שקר*] ככל שיש יותר פעולות, התוכנה איטית יותר.
  2. כשאנחנו כותבים בפייתון x = x + 1, פייתון עשויה לעשות כל מני חישובים מוזרים מאחורי הקלעים (כדי לאפשר לנו לעבוד עם מספרים ממש גדולים, לדוגמה). זה יגרור די הרבה הוראות שהמעבד צריך להריץ. נזרוק סתם מספר, נניח, 50. אז x = x + 1 בפייתון גורם למעבד להריץ 50 הוראות.
  3. אם נכתוב את אותה השורה בשפת התכנות C, כיוון שב־C תוחמים את הגודל של x ו־C מלכתחילה היא שפה שקל “לתרגם” ממנה לשפה שהמעבד יבין, המעבד יצטרך להריץ ממש מעט פעולות, נניח 1. אז x = x + 1 ב־C גורמת למעבד להריץ הוראה 1.
  4. נניח שככה אני מודד את היעילות של התוכנה שלי. כתבתי פתרון לאחד התרגילים, ואני רוצה למדוד את היעילות שלו בעזרת הביטוי x = x + 1 שרץ N פעמים. מתעוררות כמה בעיות:
    4.1. האם הגיוני להגיד שהפתרון ב־C הוא O(N) והפתרון בפייתון הוא O(50\cdot N)? בכלל, ההמרה הזו בין שורת קוד לכמות הפעולות שהמעבד יריץ היא סופר לא טריוויאלית וכשעושים אותה צריך להתחשב בכמות עצומה של נושאים תיאורטיים מורכבים מאוד. כל פעם שנרצה לקבל תחושת בטן על יעילות נצטרך לבדוק איך מחשבים את ההשוואה הזו? אנחנו אנשי מדמ"ח, אנחנו עצלנים.
    4.2. נניח שעברנו את המשוכה הזו, אבל אז מישהו סיפר לנו שקרן הפייתון הבינלאומית מימנה את הפתרון שלנו, ופתרון הפייתון שלנו רץ על מחשב כסוף ונוצץ. הפתרון שכתוב ב־C עדיין רץ על הטרנטה שקיבלנו לבת מצווה. המחשב שקרן הפייתון קנו פי 50 חזק יותר! האם עדיין הגיוני להגיד שהתוכנה שכתובה ב־C פי 50 מהירה מזו שכתובה בפייתון?
  5. אפשר להסיק מכאן שעבור כל בעיה, אם נזרוק מספיק כסף על שרתים כסופים נוצצים, נוכל לפתור אותה ביעילות עם מקדם נמוך יותר. למעשה, אפילו טרחו להוכיח את זה מתמטית.
  6. לכן כשאנחנו באים להעריך עד כמה אלגוריתם הוא “טוב”, נעיף מההערכה שלנו כל מקדם שהוא. המקדם הזה לא משרת אותנו ונקבל הערכה טובה יותר בלעדיו.
  7. מה כן מעניין? מה סדר הגודל של השינוי בזמן הריצה של התוכנית, כשאנחנו מקטינים או מגדילים את גודל הקלט שלנו.

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


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

8 לייקים

מצאתי מאמר נוסף שמסביר מצוין ובפירוט על כל אחת מהגדרות הסיבוכיות:
https://towardsdatascience.com/understanding-time-complexity-with-python-examples-2bda6e8158a7

לייק 1