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

מנהל: TA_Isana

שלח תגובה
michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

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

שליחה על ידי michal cohen » 18:20 19/05/2010

הבנתי לחלוטין איזה מבנה נתונים מחזיר לי חיפוש של איבר ב-O של 1.
אבל מה שאני לא מבינה זה שאם אחרי כל אינסרט האיברים המיוחדים משתנים לי... איך אני יכולה לעדכן אותם במבנה הזה בלכל היותר klogn?
הרי באינסרט זה במקרה הגרוע ביותר והכנסה למבנה הזה במקרה הגרוע ביותר היא k^2..
הדרך היחידה שמצאתי היא ממש לא יעילה וזה לבנות מערך בבגודל האיבר המיוחד האחרון ולהכניס את כל האיברים המיוחדים לאינדקס שלהם לפי הערך שלהם בצורה ישירה...
אבל אז לא משתמשים במבנה הנתונים הזה כי זה סתם מערך....
מה אני מפספסת?

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

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

שליחה על ידי TA_Ariel » 20:45 19/05/2010

למה ההכנסה היא k^2?

michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

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

שליחה על ידי michal cohen » 21:50 19/05/2010

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

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

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

שליחה על ידי TA_Ariel » 21:56 19/05/2010

את יכולה להתשמש בשיטה שכל ההכנסות יהיו בכל מקרה O(1) גם אם כולם באותו תא, ולכן k הכנסות יקחו O(k).

שלח תגובה

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