עבור לתוכן
View in the app

A better way to browse. Learn more.

HWzone

A full-screen app on your home screen with push notifications, badges and more.

To install this app on iOS and iPadOS
  1. Tap the Share icon in Safari
  2. Scroll the menu and tap Add to Home Screen.
  3. Tap Add in the top-right corner.
To install this app on Android
  1. Tap the 3-dot menu (⋮) in the top-right corner of the browser.
  2. Tap Add to Home screen or Install app.
  3. Confirm by tapping Install.

שאלה לגבי סיבוכיות של מציאת ערך בטבלת האש

Featured Replies

פורסם

מהי הסיבוכיות של מציאת ערך בטבלת האש עם הרבה ערכים ומעט מפתחות? האם זה עדיין 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

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים

Configure browser push notifications

Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.