שאלה על האינסרט

מנהל: TA_Isana

שאלה על האינסרט

הודעהעל ידי michal cohen » 17:20 19/05/2010

הבנתי לחלוטין איזה מבנה נתונים מחזיר לי חיפוש של איבר ב-O של 1.
אבל מה שאני לא מבינה זה שאם אחרי כל אינסרט האיברים המיוחדים משתנים לי... איך אני יכולה לעדכן אותם במבנה הזה בלכל היותר klogn?
הרי באינסרט זה במקרה הגרוע ביותר והכנסה למבנה הזה במקרה הגרוע ביותר היא k^2..
הדרך היחידה שמצאתי היא ממש לא יעילה וזה לבנות מערך בבגודל האיבר המיוחד האחרון ולהכניס את כל האיברים המיוחדים לאינדקס שלהם לפי הערך שלהם בצורה ישירה...
אבל אז לא משתמשים במבנה הנתונים הזה כי זה סתם מערך....
מה אני מפספסת?
michal cohen
 
הודעות: 87
הצטרף: 19:04 11/11/2009

Re: שאלה על האינסרט

הודעהעל ידי TA_Ariel » 19:45 19/05/2010

למה ההכנסה היא k^2?
TA_Ariel
 
הודעות: 261
הצטרף: 23:53 22/04/2009

Re: שאלה על האינסרט

הודעהעל ידי michal cohen » 20:50 19/05/2010

כי בהאש טייבל מחשבים את המקרה הגרוע ביותר כשכולם אמורים להיכנס לאותו התא...
ובהכנסה במקרה הגרוע ביותר כל האיברים ה-a*n/k מתחלפים (כי הכנסה לחלק הראשון (עד 1* n/k) גוררת שינוים של האיברים המיוחדים בכל החלקים שאח"כ)...
ואז צריך להחליף את כל k האיברים המיוחדים החדשים בטבלה וזה יוצא O(k) לכל הכנסה במקרה הגרוע ביותר...
סה"כ k^2....
michal cohen
 
הודעות: 87
הצטרף: 19:04 11/11/2009

Re: שאלה על האינסרט

הודעהעל ידי TA_Ariel » 20:56 19/05/2010

את יכולה להתשמש בשיטה שכל ההכנסות יהיו בכל מקרה O(1) גם אם כולם באותו תא, ולכן k הכנסות יקחו O(k).
TA_Ariel
 
הודעות: 261
הצטרף: 23:53 22/04/2009


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 2 אורחים