WC time for building a perfect hash
EliL 13 Feb 2011 14:55
במבחן מ2006 סמסטר א מועד ב
בשאלה 7 נשאל מה סיבוכיות מקרה גרוע הגבוהה ביותר בבניית המבנים
hash = WC O(n)
perfect hash = ?
max heap = WC O(n)
AVL = WC O(nlogn)
התשובה היתה גיבוב מושלם
למה?
דיברנו על כך שזמן הבניה של גיבוב מושלם הוא ליניארי בתוחלת.
אבל מה עם המקרה הגרוע?
איך שאני מבין את זה, בשלב ההגרלה של הפונקציות במקרה הגרוע נצטרך לעבור על חצי מהפונקציות ההאש במשפחה האוניברסלית.
כלומר התשובה לשאלה תלויה בגודל המשפחה האוניברסלית הרלוונטית, לא?
ואם היא אינסופית? המקרה הגרוע לא חסום בכלל, לא?