Ex9, Question 1

Ex9, Question 1

HilaP 27 Jan 2010 12:03

סעיף ב שואל על הזמן אמורטייזד של רצף הכי-גרוע-כלשהו, או הרצף הגרוע ביותר המתחיל עם איברים בודדים?

Re: Ex9, Question 1

Yahav 27 Jan 2010 13:56

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

הרבה פעמים זה לא ממש משנה.

אם את מסוגלת להראות, עבור מבנה נתונים כלשהו, רצף של $k$ פעולות שלוקח $\Theta(Tk)$ זמן,
כאשר $k$ גדול כרצוננו, בתנאי שמתחילים ממבנה שאינו ריק, אז הזמן $\Theta(Tk)$ בדרך כלל שולט
על זמן ההכנה של המבנה הלא ריק, ובמקרה כזה הצלחת להראות זמן ריצה $\Theta(T)$ אמורטייזד לפעולה.