פורסם 2011 בספטמבר 1214 שנים מהי הסיבוכיות של מציאת ערך בטבלת האש עם הרבה ערכים ומעט מפתחות? האם זה עדיין O(1) ?למשל מספר התלמידים בישראל כאשר המפתחות זה ציונים וצריך למצוא סטודנט.תודה לעוזרים.
פורסם 2011 בספטמבר 1214 שנים דבר ראשון, במקרה כזה חייבים להשתמש בהאש פתוח (כלומר, בכל אינדקס בטבלת ההאש יושבת רשימה של הערכים המתאימים למפתח הזה). סיבוכיות מציאת איבר בהאש היא כגודל הרשימה הזו.במקרה הטוב ביותר, הערכים מפוזרים באופן אחיד בין המפתחות, ככה שאם יש N ערכים ו-K מפתחות, אז לכל מפתח משויכים בערך N/K ערכים, ולכן הסיבוכיות של מציאת ערך תהיה (O(N/K.במקרה הגרוע ביותר יהיה מפתח שמכיל את רוב הערכים (כלומר, סדר גודל של N), ואז הסיבוכיות של מציאת ערך היא (O(N.
פורסם 2011 בספטמבר 1314 שנים אם זה רשימה מקושרת אז אכן (O(N. ניתן ליצור עץ חיפוש כשבונים את טבלת הגיבוב.
פורסם 2011 בספטמבר 1314 שנים מחבר דבר ראשון, במקרה כזה חייבים להשתמש בהאש פתוח (כלומר, בכל אינדקס בטבלת ההאש יושבת רשימה של הערכים המתאימים למפתח הזה). סיבוכיות מציאת איבר בהאש היא כגודל הרשימה הזו.במקרה הטוב ביותר, הערכים מפוזרים באופן אחיד בין המפתחות, ככה שאם יש N ערכים ו-K מפתחות, אז לכל מפתח משויכים בערך N/K ערכים, ולכן הסיבוכיות של מציאת ערך תהיה (O(N/K.במקרה הגרוע ביותר יהיה מפתח שמכיל את רוב הערכים (כלומר, סדר גודל של N), ואז הסיבוכיות של מציאת ערך היא (O(N.O(n/k) זו התשובה שחיפשתי לדעתי כאשר אני יוצא מנקודת הנחה שהפונקציה שלי מעניקה פיזור אחיד.אם זה רשימה מקושרת אז אכן (O(N. ניתן ליצור עץ חיפוש כשבונים את טבלת הגיבוב.אתה מתכוון לייצג את טבלת האש ע"י עץ חיפוש ואז שחיפוש יעלה לוג של אן?
פורסם 2011 בספטמבר 1314 שנים תייצג את טבלת הגיבוב לפי איך שאתה עומד להשתמש בה. יצירת העץ גם עולה לך בסיבוכיות.וכן, לרוב חיפוש בעץ חיפוש (במקרה הממוצע) יעלה (log(n
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.