עמוד 1 מתוך 1

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

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

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

הודעהפורסם: 19:45 19/05/2010
על ידי TA_Ariel
למה ההכנסה היא k^2?

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

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

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

הודעהפורסם: 20:56 19/05/2010
על ידי TA_Ariel
את יכולה להתשמש בשיטה שכל ההכנסות יהיו בכל מקרה O(1) גם אם כולם באותו תא, ולכן k הכנסות יקחו O(k).