הכנסה

מנהל: TA_Isana

שלח תגובה
ilyal
הודעות: 63
הצטרף: 10:27 30/03/2009

הכנסה

שליחה על ידי ilyal » 02:31 22/05/2010

אפשר איזה כיוון חשיבה?

תודה

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: הכנסה

שליחה על ידי TA_Ariel » 02:47 22/05/2010

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

ilyal
הודעות: 63
הצטרף: 10:27 30/03/2009

Re: הכנסה

שליחה על ידי ilyal » 20:43 23/05/2010

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

תודה.

שלח תגובה

חזור אל “- מבני נתונים 2010”