מהי הסיבוכיות של מציאת ערך בטבלת האש עם הרבה ערכים ומעט מפתחות? האם זה עדיין O(1) ?

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

תודה לעוזרים.

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

במקרה הטוב ביותר, הערכים מפוזרים באופן אחיד בין המפתחות, ככה שאם יש N ערכים ו-K מפתחות, אז לכל מפתח משויכים בערך N/K ערכים, ולכן הסיבוכיות של מציאת ערך תהיה (O(N/K.

במקרה הגרוע ביותר יהיה מפתח שמכיל את רוב הערכים (כלומר, סדר גודל של N), ואז הסיבוכיות של מציאת ערך היא (O(N.

אם זה רשימה מקושרת אז אכן (O(N. ניתן ליצור עץ חיפוש כשבונים את טבלת הגיבוב.

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

במקרה הטוב ביותר, הערכים מפוזרים באופן אחיד בין המפתחות, ככה שאם יש N ערכים ו-K מפתחות, אז לכל מפתח משויכים בערך N/K ערכים, ולכן הסיבוכיות של מציאת ערך תהיה (O(N/K.

במקרה הגרוע ביותר יהיה מפתח שמכיל את רוב הערכים (כלומר, סדר גודל של N), ואז הסיבוכיות של מציאת ערך היא (O(N.

O(n/k) זו התשובה שחיפשתי לדעתי כאשר אני יוצא מנקודת הנחה שהפונקציה שלי מעניקה פיזור אחיד.

אם זה רשימה מקושרת אז אכן (O(N. ניתן ליצור עץ חיפוש כשבונים את טבלת הגיבוב.

אתה מתכוון לייצג את טבלת האש ע"י עץ חיפוש ואז שחיפוש יעלה לוג של אן?

תייצג את טבלת הגיבוב לפי איך שאתה עומד להשתמש בה. יצירת העץ גם עולה לך בסיבוכיות.

וכן, לרוב חיפוש בעץ חיפוש (במקרה הממוצע) יעלה (log(n