skip lists

מנהל: TA_Isana

skip lists

הודעהעל ידי zoran » 11: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 לאיבר

כמה איברים אמורים להיות ברמה הכי גבוהה בממוצע?(לא הרמה של מינוס אינסוף, אינסוף)
והאם הניתוח שלי נכון
תודה ענבל
zoran
 
הודעות: 30
הצטרף: 21:18 10/11/2009

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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 3 אורחים

cron