skip lists

מנהל: TA_Isana

שלח תגובה
zoran
הודעות: 30
הצטרף: 21:18 10/11/2009

skip lists

שליחה על ידי zoran » 12:12 16/07/2010

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

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

שלח תגובה

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