דף 1 מתוך 1

הכנסה

נשלח: 02:31 22/05/2010
על ידי ilyal
אפשר איזה כיוון חשיבה?

תודה

Re: הכנסה

נשלח: 02:47 22/05/2010
על ידי TA_Ariel
יש לך klogn זמן להכנסה. תחשוב מה זה אומר על מבנה נתונים שלך.
בשביל לענות בO(1) על ElementAt כנראה שאתה צריך O(k) מבנה נתונים.
מה שאומר שאתה צריך להשתמש במבנה שדורש logn בהכנסה (עץ AVL או ערימה) והכנסת איבר אחד יכולה לגרור שרשרת הכנסות לכל המבנים.
בנוסף אתה אמור לטפל בשאילתות מסוג isElementAtSpecialPLace שבשבילם אתה צריך מבנה נתונים שונה, שלפי זמני הריצה אמור לפעול בזמן ממוצע.

Re: הכנסה

נשלח: 20:43 23/05/2010
על ידי ilyal
אם לאחר ההכנסה ה - n/k אינו משתנה, אז באמת ניתן לעמוד בזמנים ולעדכן את המבנה.
מה קורה כאשר לאחר הכנסה n/k כן משתנה. אני לא רואה שום דרך ליישם את השינוי מלבד איתחול.
אני מפספס משהו?

תודה.