עמוד 1 מתוך 1

skip lists

הודעהפורסם: 11:12 16/07/2010
על ידי zoran
בתרגול 7 שאלה 2 ביקשו למצוא אלגוריתם בזמן ריצה ממוצע של logn למציאת האיבר הk בגודלו ברשימת דילוגים S עם n איברים.
הפתרון היה להוסיף לכל איבר ברמה Si שדה שבו אנו שומרים את מס' האיברים ברמה התחתונה עד לאיבר העוקב שלו ברמה Si. האלגוריתם רץ בlogn אבל האתחול הרבה יותר ואליו לא התייחסנו.
השאלה שלי היא כמה זמן עולה לאתחל מבנה כזה בממוצע?
לרמה הגבוהה נאמר יש b איברים לכל איבר אם נסכום את כל האתחולים על האיברים בכל הרמות שלוlog(n!)= log(n)+log(n-1)+...+1
לרמה השניה בגובהה יש פי 2 איברים אבל בb כבר טיפלנו אז שוב b איברים כפול (!(log((n-1 לאיבר

כמה איברים אמורים להיות ברמה הכי גבוהה בממוצע?(לא הרמה של מינוס אינסוף, אינסוף)
והאם הניתוח שלי נכון
תודה ענבל