טבלת גיבוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Badidipedia (שיחה | תרומות) אין תקציר עריכה |
Badidipedia (שיחה | תרומות) אין תקציר עריכה |
||
שורה 52:
כמו במבנה הנתונים [[מערך (מבנה נתונים)|מערך]], טבלת הגיבוב מאפשרת בדיקת נתון ב[[סיבוכיות זמן]] ממוצעת של (Θ(1 - ללא תלות במספר האלמנטים בטבלה. אולם, במקרה הגרוע ביותר, הבדיקה עשויה להתבצע בסיבוכיות זמן טובה פחות, של (O(n, כאשר n מייצג את מספר האיברים בטבלה. בהשוואה למבני מערך, טבלאות גיבוב מועילות כאשר יש לאחסן מספר גדול של רשומות ובמיוחד כאשר גודל קבוצת הנתונים ניתן לחיזוי.
קיימות טבלאות מיוחדות הקרויות '''טבלאות גיבוב מושלמות''', המאפשרות השגת נתון ב-(O(1 במקרה הגרוע ביותר. טבלה זו קלה לתחזוק, אך נדרש זמן גדול לבנייתה הראשונית והיא דורשת מקום מורחב יחסית לטבלת גיבוב רגילה.
== שיטות גיבוב ==
עבור טבלה סגורה, ניתן להשתמש במבנה הנתונים [[רשימה מקושרת]] ולמרות שבמקרה הגרוע, היעילות תהיה <math>\ O(n)</math> עבור כל אחת משלושת הפעולות, קלות התפישה של פעולת הרשימות המקושרות ותכנותם, יכולים לפצות על כך. ניתן להשתמש גם ב[[עץ חיפוש]] מאוזן כמו [[עץ AVL]] ו[[עץ B Plus|עץ B+]] שיקטינו את החיפוש במקרה הגרוע ל <math>\ O(\log n)</math>. ב[[מערכת זמן אמת|מערכות זמן אמת]] בהם זמן ביצוע פעולה הוא קריטי גם במקרה הגרוע, בחירה במבני נתונים אלו יכולה לשפר את ביצועי המערכת.
==שימושים שונים לטבלאות גיבוב==
| |||