שאלה לגבי סיבוכיות זמן
- פותח הנושא ronib25
- פורסם בתאריך
אני מסכים עם הסיבוכיות, השאלה היא מדוע היא כזו..
לפי מה שאני חושב היא מכיוון שההתחלה היא תמיד ביחידת חישוב 1 שנדרשת לחלק למקרה הגרוע ביותר של n מעבדים שירוצו במקביל. לכן על מנת לחלק ל n מעבדים יש לעבור על המחרוזת שאורכה הינו n.
מצד שני אפשר להגיד שבריצה המקבילית החישוב הינו O(1 כפול n מעבדים ושוב מקבלים O(n. לכן רציתי לדעת מאיפה הסיבוכיות מגיעה באופן ספציפי ממה שציינתי..
לפי מה שאני חושב היא מכיוון שההתחלה היא תמיד ביחידת חישוב 1 שנדרשת לחלק למקרה הגרוע ביותר של n מעבדים שירוצו במקביל. לכן על מנת לחלק ל n מעבדים יש לעבור על המחרוזת שאורכה הינו n.
מצד שני אפשר להגיד שבריצה המקבילית החישוב הינו O(1 כפול n מעבדים ושוב מקבלים O(n. לכן רציתי לדעת מאיפה הסיבוכיות מגיעה באופן ספציפי ממה שציינתי..
למיטב זיכרוני
האפשרות למקבל ביצוע של אלגוריתם אינה משפיע על הסיבוכיות שלו, משום שהסיבוכיות בפועל היא תאורטית - מתמטית.
O (או גדולה) נותנת סדר גודל, ולא זמן אמתי של ריצה (מהמילה האנגלית order).
 
כך למשל, זה לא משנה אם האלגוריתם צריך לבצע 100 פעולות על כל תא במערך בגודל n או רק פעולה אחת על כל תא.
כל עוד הוא צריך לעבור על המערך רק פעם אחת, הסיבוכיות תהיה בגול O
.
 
בגלל זה גם O == O(2n)
אז גם O == O(1/2n)
 
כנ"ל במקרה הזה: בין אם תפזר את העבודה בין מעבדים \ ליבות ובין אם תעשה אותה בתור, סדר גודל הזמן שדרוש הוא ביחס ישיר לקלט, כלומר O.
 
יכול להיות שיש ניסוח אקדמי יותר נכון, ומה שכתבתי לך לא יתקבל כתשובה במבחן \ שיעורי בית, אבל העיקרון תופס.
האפשרות למקבל ביצוע של אלגוריתם אינה משפיע על הסיבוכיות שלו, משום שהסיבוכיות בפועל היא תאורטית - מתמטית.
O (או גדולה) נותנת סדר גודל, ולא זמן אמתי של ריצה (מהמילה האנגלית order).
 
כך למשל, זה לא משנה אם האלגוריתם צריך לבצע 100 פעולות על כל תא במערך בגודל n או רק פעולה אחת על כל תא.
כל עוד הוא צריך לעבור על המערך רק פעם אחת, הסיבוכיות תהיה בגול O
. 
בגלל זה גם O
== O(2n)אז גם O
== O(1/2n) 
כנ"ל במקרה הזה: בין אם תפזר את העבודה בין מעבדים \ ליבות ובין אם תעשה אותה בתור, סדר גודל הזמן שדרוש הוא ביחס ישיר לקלט, כלומר O
. 
יכול להיות שיש ניסוח אקדמי יותר נכון, ומה שכתבתי לך לא יתקבל כתשובה במבחן \ שיעורי בית, אבל העיקרון תופס.
זה נכון אם מספר המעבדים קבוע.
אם מספר המעבדים אינסופי (או שהוא תלוי בגודל הקלט), הסיבוכיות בהחלט עשויה להשתנות.
(זה מה שעומד מאחורי התחום התיאורטי של חישוב מקבילי).
 
במקרה של הקוד בשאלה (לא קראתי בעיון, אבל מרפרוף נראה שהוא מקבל מערך, ועושה עיבוד טריוויאלי על תוצאות הפעלה רקורסיבית על שני החצאים שלו), בעזרת n מעבדים, אפשר לבצע אותו בזמן log.
אם מספר המעבדים אינסופי (או שהוא תלוי בגודל הקלט), הסיבוכיות בהחלט עשויה להשתנות.
(זה מה שעומד מאחורי התחום התיאורטי של חישוב מקבילי).
 
במקרה של הקוד בשאלה (לא קראתי בעיון, אבל מרפרוף נראה שהוא מקבל מערך, ועושה עיבוד טריוויאלי על תוצאות הפעלה רקורסיבית על שני החצאים שלו), בעזרת n מעבדים, אפשר לבצע אותו בזמן log
.ניתן להגיד שלכל אות במחרוזת - יוצרים תהליכון
שמבצע פעולת PAIR
ובנוסף בעת האיחוד יש פעולת PAIR
כך שסך העיבוד - הוא (O(N
אם יש מעבד אחד וזמן ביצוע FORK+ PAIR הוא Z
(O(N זה הWORST CASE
אם יש N מעבדים,
אז O(LOG_N)*Z
מכיוון שזו לא הנחה סבירה - זה כנראה לא המצב,
במקרה הסביר, מספר המעבדים - הוא רק קבוע...
שמבצע פעולת PAIR
ובנוסף בעת האיחוד יש פעולת PAIR
כך שסך העיבוד - הוא (O(N
אם יש מעבד אחד וזמן ביצוע FORK+ PAIR הוא Z
(O(N זה הWORST CASE
אם יש N מעבדים,
אז O(LOG_N)*Z
מכיוון שזו לא הנחה סבירה - זה כנראה לא המצב,
במקרה הסביר, מספר המעבדים - הוא רק קבוע...
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.