שאלה לגבי זמן הריצה של Insert - האם k^2 תקין?

מנהל: TA_Isana

שלח תגובה
boazarad
הודעות: 17
הצטרף: 15:16 26/10/2009

שאלה לגבי זמן הריצה של Insert - האם k^2 תקין?

שליחה על ידי boazarad » 23:58 24/05/2010

אנחנו מנסים כרגע לממש את המבנה בעזרת K ערימות מקסימום.
על פניו, לאחר כמה תוספות ושיפורים למבנה הערימה, אנחנו מסוגלים לעמוד ברוב הדרישות של זמן הריצה.

נוצרת בעיה - בInsert כאשר [n/k] גדל. במצב זה, לk-1 מהערימות שלנו "חסר" איבר, ויש להשלים אותו מהערימה הגדולה ביותר.
לכן צריך לקחת k-1 איברים, ולדחוף אותם לערימה השניה בגדולה, מה שייצור overflow של k-2 איברים, אותם נדחוף לערימה השלישית בגודלה וכן הלאה.
סה"כ אנחנו מבצעים (k-1+k-2+k-3...+1) דחיפות.
אפילו אם יעילות הדחיפה וההוצאה מהעירמה היא מסדר גודל (1)O - יעילות הInsert הספציפי הזה (שהיא כמובן המקרה הגרוע) היא מסדר גודל של (O(k^2.

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

סטרז'
הודעות: 28
הצטרף: 23:25 26/10/2009

Re: שאלה לגבי זמן הריצה של Insert - האם k^2 תקין?

שליחה על ידי סטרז' » 01:37 25/05/2010

לפי הבנתי של העבודה הזאת אתה קצת מסתכל על זה לא נכון:
נניח במצב של 14 איברים ו k=3 יהיה לך 3 ערמות , נניח ערימה ראשונה ושניה עם 5 איברים וערימה שלישית עם 4 איברים
כלומר תמיד יהיה לך מצב (חוץ מכאשר n/k יוצא מספר שלם) שיהיו לך ערימות יותר קטנות.
הכיוון של המבנה שלך נכון , אבל השינוים שאתה אומר שצריך לעשות בזמן הכנסה הם לא נכונים , תחשבו על מקרים בהם ההכנסה תפגע בערכים ה"מיוחדים" ואיך לטפל בכל מקרה
רמז : זה אכן קשור למספר האיברים בערימה שאליה אתה מכניס ולמספר האיברים בערימות האחרות

boazarad
הודעות: 17
הצטרף: 15:16 26/10/2009

Re: שאלה לגבי זמן הריצה של Insert - האם k^2 תקין?

שליחה על ידי boazarad » 01:42 25/05/2010

כן, נפל לנו האסימון הזה לפני שעה, נראה לי שנסתדר מכאן - תודה!

palpal
הודעות: 7
הצטרף: 21:39 02/11/2009

Re: שאלה לגבי זמן הריצה של Insert - האם k^2 תקין?

שליחה על ידי palpal » 16:23 26/05/2010

אהלן חבר'ה, יש לי בדיוק אותה בעייה כמו לבועז, רק שלא הבנתי את הפתרון החלקי שניתן פה.
אם אפשר לחדד עוד קצת את הנקודה.
תודה.

boazarad
הודעות: 17
הצטרף: 15:16 26/10/2009

Re: שאלה לגבי זמן הריצה של Insert - האם k^2 תקין?

שליחה על ידי boazarad » 18:14 26/05/2010

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

כל השאלה שלי נבעה מאי הבנה של התנהגות הפונקציה שאנחנו נדרשים ליישם.

מקווה שזה עוזר.

שלח תגובה

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