30-01-2012, 00:47
|
|
|
|
חבר מתאריך: 14.12.09
הודעות: 9,751
|
|
מה שאתה אומר זה בדיוק זה.
הגודל הסופי שלך הוא N. נגיד שזה 700.
ההעתקה האחרונה שאתה עושה היא ממערך בגודל 512 למערך בגודל 1024 (ואז ממלא עוד 188 איברים).
ההעתקה הקודמת היא ממערך בגודל 256 למערך בגודל 512 (ואז ממלא עוד 256 איברים).
ההתעקה הקודמת היא ממערך בגודל 128 למערך בגודל 256 (ואז ממלא עוד 128 איברים).
וכך הלאה.
כמה העתקות יש לנו בסך-הכל?
2+4+8+16+32+64+128+256+512=1022.
עכשיו, יש פה קפיצות, ולכן גם בפונקציה של מספר ההעתקות כתלות בגודל המערך הסופי של קפיצות.
גם אם N היה 730 או 750 או 1000 מספר ההעתקות היה 1022.
אבל בוא נתעלם מזה. לצורך העניין נגיד ש-N הוא תמיד חזקה של 2 (כי אתה משלם אותו דבר על כל גודל של N שגדול מהחזקה הקודמת של 2).
בעצם השאלה שלך הופכת להיות, מה הביטוי לסכום של חזקות 2 עד מספר מסוים. התשובה היא:
[TEX]\sum_{1}^{n} 2^n = 2^{n+1}-1[/TEX]
מאחר ואין לך את המערך בגודל 1, אלא אתה מתחיל מגודל 2, זה בעצם:
[TEX]\left ( \sum_{1}^{n} 2^n \right ) - 1 = 2^{n+1}-2[/TEX]
איך מוכיחים את זה? זה ביטוי די מוכר, אבל אם בא לך להוכיח את זה, אני מניח שאפשר באינדוקציה.
נניח שהביטוי נכון עבור [TEX]n=k[/TEX], כלומר:
[TEX]\sum_{1}^{k} 2^k = 2^{k+1}-1[/TEX]
ונוכיח שהוא נכון עבור [TEX]n=k+1[/TEX], כך:
[TEX]\sum_{1}^{k+1} 2^{k+1} = 2^{k+1+1}-1[/TEX]
[TEX]2^{k+1} + \sum_{1}^{k} 2^{k} = 2 \cdot 2^{k+1} - 1[/TEX]
[TEX]2^{k+1} + \sum_{1}^{k} 2^{k} = 2^{k+1} + 2^{k+1} - 1[/TEX]
[TEX]\sum_{1}^{k} 2^{k} = 2^{k+1} - 1[/TEX]
השורה האחרונה נכונה לפי הנחת האינדוקציה.
השאלה השנייה היא כמה זמן לוקחת ההקצאה. התשובה היא שאתה לא יודע.
או שתניח לצורך התרגיל שהיא קבועה (זה נכון בהרבה מקרים). או שתניח שהיא תלויה לינארית ב-N (זה גם נכון לפעמים).
במציאות, להקצות מעט זיכרון (נגיד, 100 int-ים) לוקחת זמן קבוע. הקצאה גדולה יותר תיקח יותר זמן, בתלות שהיא בערך לינארית (עם קפיצות דומות). אבל לפעמים ברגע שאתה חוצה סף מסוים, פתאום זה לוקח המון זמן. במציאות, בודקים את הביצועים בזמן ולא את הסיבוכיות, כי גודל הזיכרון הוא נתון ולא שואף לאינסוף (לדוגמה, אנחנו מניחים שמע"ה רצה על חומרה שיש לה בין ג'יגה זיכרון ל-512GB, אז אנחנו דואגים שבממוצע (או amortized), הזמן יעמוד בסף מסוים.
(לאו דווקא פרטים אמיתיים: )
תחשוב שיכול להיות שלמערכת נוח תמיד להקצות לך לפחות PAGE, ככה שהקצאה של כל כמות זיכרון שקטנה מ-4KB לוקחת אותו זמן. (ככה שבמספרים מאוד קטנים זה קבוע.)
ברגע שאתה מקצה יותר, הקצאה של כל דף נוסף לוקחת יותר זמן. (ככה שזה תלוי לינארית, עם קפיצה בכל פעם שעוברים כפולה של 4KB.)
מצד שני, אם נגמר לנו המקום בטבלה שבה אנחנו שומרים את המידע על הזיכרון שהוקצה, ההקצאה יכולה פשוט להיכשל (מבחינתי זה שקול ל'אינסוף זמן').
ולפעמים קורים דברים אחרים.
_____________________________________
(קרדיט למרשי)
אמר לה ינאי מלכא לדביתיה אל תתיראי מן הפרושין ולא ממי שאינן פרושין אלא מן הצבועין שדומין לפרושין שמעשיהן כמעשה זמרי ומבקשין שכר כפנחס
אמר פסטן: שניהם גרועים, אבל עדיף להיות טיפש מאשר שקרן.
|