תרגיל 4 שאלה 3

מנהל: TA_Isana

תרגיל 4 שאלה 3

הודעהעל ידי roie » 18:36 09/06/2009

ניתן להשתמש ב skiplist כדי ליצור את Find(k) ושהזמן ריצה שלו יהיה
expected log(n) ?
roie
 
הודעות: 32
הצטרף: 21:35 15/12/2008

הודעהעל ידי roie » 12:01 10/06/2009

כבר לא חשוב,יש דרך לעשות את זה רק עם עץ avl אחד...
roie
 
הודעות: 32
הצטרף: 21:35 15/12/2008

הודעהעל ידי TA_Lena » 12:03 10/06/2009

לא, הזמני ריצה המצוינים בשאלה אלו זמני הריצה הדרושים במקרה הגרוע, ז"א למשל, את הפעולה של find(k צריך לבצע בזמן של O(log n במקרה הגרוע ולא במקרה הממוצע.
TA_Lena
 
הודעות: 141
הצטרף: 13:46 22/04/2009


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

מי מחובר

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