תרגיל 4 שאלה 3

מנהל: TA_Isana

שלח תגובה
roie
הודעות: 32
הצטרף: 21:35 15/12/2008

תרגיל 4 שאלה 3

שליחה על ידי roie » 19:36 09/06/2009

ניתן להשתמש ב skiplist כדי ליצור את Find(k) ושהזמן ריצה שלו יהיה
expected log(n) ?

roie
הודעות: 32
הצטרף: 21:35 15/12/2008

שליחה על ידי roie » 13:01 10/06/2009

כבר לא חשוב,יש דרך לעשות את זה רק עם עץ avl אחד...

TA_Lena
הודעות: 141
הצטרף: 14:46 22/04/2009

שליחה על ידי TA_Lena » 13:03 10/06/2009

לא, הזמני ריצה המצוינים בשאלה אלו זמני הריצה הדרושים במקרה הגרוע, ז"א למשל, את הפעולה של find(k צריך לבצע בזמן של O(log n במקרה הגרוע ולא במקרה הממוצע.

שלח תגובה

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