נושא: ניתוח סיבוכיות זמן ומקום

נשלח בתאריך: 11 April 2007 בשעה 22:10 | IP רשוּם

אם ב SKIPLIST מספר הרמות המקסימלי של כל קודקוד הוא LOG מספר הקודקודים הקיימים...

כלומר מספר הרמות שיכול לעלות הקודקוד ה N הוא LOGN רמות...

במקרה הגרוע למרות שמדובר בהטלת מטבע בכל החלטה האם לעלות רמה... יתכן מצב שבו יווצר SKIPLIST מעין משולש שהאיבר הראשון קיים רק ברמה הראשונה והאיבר האחרון קיים רק ברמה האחרונה כיצד זה משפיע על החיפוש?...

ועוד שאלה אם מגדירים מראש שבכל קודקוד זוגי עולים רמה.... כלומר ברמה ה N קיים רק קודקוד 1 וברמה הראשונה N קודקודים... איך זה משפיע במקרה הגרוע על הסיבוכיות?...

כלומר ללא הטלת מטבע

כלומר אם הדבר הזה ידוע מראש על אותו יריב איך הוא יכול להאט את קצב החיפוש...