שלום,

יש לי שאלה שאני לא בטוח לגביה (שפת התיכנות היא C, אבל השאלה לא קשורה ישירות לתחביר):

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

השאלה היא - מהו סדר גודל זמן הריצה?
תכל'ס עיקר העבודה פה הוא העתקת המידע מהמערך ה"ישן" לחדש.
אני חושב שזה סדר גודל של המערך הסופי, אבל אני לא יודע איך לנסח את זה כתשובה "מוכחת".
לקחתי דוגמה של מה קורה אם המשתמש מעוניין להכניס 100 מספרים:
מספר ההעתקות הוא 2 + 4 + 8 + 16 + 32 + 64, סה"כ 126.
אפשר להגיד שזה סדר גודל של המערך הסופי, כלומר O(n)‎, כאשר n הוא גודל המערך הסופי, כמובן.

אז, האם אני צודק? אם כן, איך מראים את זה בצורה נורמלית?
ואם לא, אשמח להבהרות.

תודה

אתה צודק, כי אתה כל פעם מעתיק חזקה של 2 איברים (החזקה כל פעם גדלה ב-1), ואתה עושה את זה בקירוב log n פעמים, ואז הטור שאתה מחשב הוא (ולצורך העניין נניח לרגע ש-n הוא חזקה של 2):

[tex]\sum_{i=1}^{\log n}2^i=2(2^{\log n}-1)=2(n-1)=2n-2=O(n)[/tex]

מה שאתה אומר זה בדיוק זה.

הגודל הסופי שלך הוא 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.)
מצד שני, אם נגמר לנו המקום בטבלה שבה אנחנו שומרים את המידע על הזיכרון שהוקצה, ההקצאה יכולה פשוט להיכשל (מבחינתי זה שקול ל'אינסוף זמן').
ולפעמים קורים דברים אחרים.

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

או זה

איזה כיף לשאול פה שאלות ולקבל תשובות לעניין.

תודה רבה לשניכם!