סיבוכיות מקום (מבוא למדעי המחשב)

[602]

שלום,

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

http://i.imgur.com/ja3lDXI.png

איך הייתם מחשבים עבורה את S(n)?

(או במילים אחרות אילו דברים "מוסיפים" לסיבוכיות המקום.)

 

תודה מראש =]

[stanly]

דברים שתופסים זכרון בגודל שתלוי באורך הקלט.

 

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

כל קריאה צורכת גודל קבוע של זיכרון ולכן ס"כ סיבוכיות מקום תהייה O של מספר הקריאות הרקורסיביות.

[602]

תודה. טוב הדוגמה למעלה הייתה יחסית פשוטה, יש דברים כמו זה:

http://i.imgur.com/Y8Xhgje.png שאין לי מושג מאיפה להתחיל לחשב את הסיבוכיות.

יש איזושהי דרך שיטתית לזה (או לפחות דרך נוחה להסתכל על הדברים האלה)?

[ohad]

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

לכן סיבוכיות המקום היא O של מספר הקריאות הרקורסיביות.

(מניתוח שטחי של הקוד זה O(log n)  z כי כל פעם הפונקציה נקראת על חצי מהמערך)

[602]

זה באמת O(logn)i, אבל לא הבנתי למה.

כל פעם הפונקציה מבצעת שתי קריאות, אחת על כל המערך, ואחת על חצי מערך.

בנוסף, איך בכלל מתייחסים ללולאה הזאת בסוף? היא לא תלויה ב-n באופן ישיר, האם ניתן לומר כי כל הלולאה היא O(1)i? (גם זמן וגם מקום)

[ohad]

שים לב ששתי הקריאות הן על חצי מערך.

דמיין את עץ הקריאות לרקורסיה כל פעם הקרא חצי ולכן גובה העץ שהוא סיבוכיות המקום הוא O(log n) כמו פה:

http://homepages.ius.edu/RWISMAN/C455/html/activity/activity-4.gif

זאת כיוון שבבת אחת "פתוחות" O(log n) רקורסיות שכל אחת משתמשת ב O(1) מקום.

 

הלולאה בסוף בכלל לא רלוונטית למקום נוסף, היא משתמש במקום נוסף קבוע בלבד.

[602]

תודה רבה! עכשיו יותר מובן אבל עדיין מעורפל.

איך אתה יודע שהקריאות הן על חצי מערך? (הקריאה השנייה שולחת חצי מערך, אבל הקריאה הראשונה שולחת את כל המערך רק עם פרמטר n/2 במקום n. אם הבנתי נכון אתה אומר שבכל אחד מהמקרים האלה הפונקציה "מתעסקת" רק עם חצי מהמערך...)

בנוגע לעץ רקורסיות, למה יש כל צומת מתפצלת ל-4 צמתים ולא ל-2?

[ohad]

צודק, תדמיין שזה מתחלק רק ל2 (התמונה ההיא עוסקת במקרה אחר).

הפונקצייה בכלל לא שולחת מערך, היא רק שולחת מצביע וגודל,

אבל זה לא רלוונטי, מה שמעניין אותך זה מה יהיה עומק הרקורסיה המקסימלי,

וכיוון שהיא כל פעם מטפלת בחצי מערך ואח"כ בחצי של החצי וכו', עד שהיא תגיע לאיבר אחד יהיו O(log n) קריאות, וזה העומק.

[602]

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

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

(זה נראה לי הגיוני שגם היא תהיה logn: בכל קריאה יש שתי קריאות על n/2, וחוץ מזה שאר הפקודות הן זמן קבוע. מסתבר שזה לא נכון.)

[602]

עריכה: אוקיי הסתדרתי עם הסיבוכיות זמן:

http://www.codecogs.com/gif.latex?T(n)=c_%7B1%7D+c_%7B2%7Dn+2T(n/2) (כאשר c_2 כפול n נובע מהלולאה)

נציב T(n/2) ונקבל:

http://www.codecogs.com/gif.latex?T(n)=3c_%7B1%7D+2c_%7B2%7Dn+2%5E%7B2%7DT(n/4)

נמשיך ונמשיך... ולבסוף נקבל:

http://www.codecogs.com/gif.latex?T(n)=Qc_%7B1%7D+kc_%7B2%7Dn+2%5E%7Bk%7DT(n/k) (לא רציתי לרשום את Q במפורש, זה פשוט סכום סדרה הנדסית, שבחשבון הסופי היא מסדר גודל של n ולכן לא משנה לנו. Q לא קבוע והוא תלוי ב-k.)

נציב http://www.codecogs.com/gif.latex?k=logn ונקבל:

http://www.codecogs.com/gif.latex?T(n)=Qc_%7B1%7D+c_%7B2%7Dnlogn+nT(1), ונקבל http://www.codecogs.com/gif.latex?T(n)%5Cin%20O(nlogn).

[אורח טל]

לא הבנתי איך הלולאה נותנת c2*n הרי היא תלויה ב-num1 ו-num2 וזה נראה כאילו הלולאה היא logn

[602]

ממבט שטחי: נראה שהלולאה תרוץ מקסימום n/2 פעמים, אאל"ט בגלל זה רשמתי c_2*n (בד"כ תרוץ פחות כמובן).

(בהנחה ששנינו התכוונו למספר האיטרציות שהלולאה עושה, אני לא רואה סיבה שהיא תרוץ logn. אין פה משהו שנחצה כל איטרציה, אלא פשוט מוסיפים 1 ל-i/מורידים 1 מ-j ככה עד שאחד מהם מגיע ל-half, במקרה הגרוע שניהם יגיעו יחדיו ל-half וזה יקח half=n/2 איטרציות.)

[אורח נדב]

שאלה מעניינת הרבה יותר - מה סיבוכיות הזמן של הפונקציה heartbeat שלמעלה...

הבעייתית היא ש"עץ הקריאות" מתפצל לפעמים ל-2 ענפים, ולפעמים לענף בודד - אם n מתחלק ב-3.

לאחר ניתוח כמה שלבים ניתן להבחין שמספר הקריאות בכל "מפלס" מתאר בדיוק סדרת פיבונאצ'י.

סכום סדרת פיבונאצ'י שואף (ומתנהג כמו) לסכום סדרה הנדסית שמנתה פי (phi = יחס הזהב, בערך 1.618).

כלומר סיבוכיות הזמן היא תטא של פי בחזקת n.