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

[boazarad]

אנחנו מנסים כרגע לממש את המבנה בעזרת 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 - איננו יכולים להניח כי היעילות שהגענו אליה אכן עומדת בתנאי התרגיל.
האם מדובר במצב תקין?
ואם לא - האם ניתן לעמוד בתנאי השאלה בעזרת מבנה בסגנון הזה, או שאנחנו בכלל לא בכיוון?

[סטרז']

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

[boazarad]

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

[palpal]

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

[boazarad]

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

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

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