עבודה 6 - שאלה 1ג

מנהל: TA_Isana

שלח תגובה
xozyain
הודעות: 21
הצטרף: 00:41 25/10/2007

עבודה 6 - שאלה 1ג

שליחה על ידי xozyain » 23:35 12/07/2009

יש לי בעיה עם האלגוריתם שהוצע כאשר מנתחים זמן ריצה מקסימלי.
נניח ויש לנו 100 מפתחות מהצורה 1.0000xxx כאשר xxx מסמלים את הספרות שמבדילות בין האיברים. נניח k=2.
כל האיברים יכנסו ל-bucket השני בריצה הראשונה. וגם באיטרציה השניה. רק באיטרציה השלישית יתחילו להיכנס לבאקטים שונים....
ניתוח של זמן ריצה מקסימלי מאפשר להניח כי האיברים אינם מפוזרים באופן אחיד (בערך) ואז האלגוריתם ימשיך באופן רקסורבי כמות מחזורים התלויה בכמות האפסים שאחרי הנקודה העשרונית (עבור הדוגמא שלי). כלומר זה לא תלוי רק ב-k ו-n.
אני מבין שעבור זמן ריצה ממוצע לא יהיה מצב כזה שהמפתחות כל כך קרובים בערכם, אבל איך מנתחים את המקרה הגרוע במצב כזה???

TA_Guy
הודעות: 21
הצטרף: 09:03 07/07/2009

Re: עבודה 6 - שאלה 1ג

שליחה על ידי TA_Guy » 09:41 14/07/2009

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

שלח תגובה

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