טבלת השוואה
טבלה זו משווה את מהירות הפעולות על מבני הנתונים השונים. אם לא
מצוין אחרת, היעילות היא של המקרה הגרוע ביותר.
| מבנה נתונים |
הוספת איבר |
מחיקת איבר |
חיפוש איבר |
| מערך |
בסוף המערך: (O(1
באמצע: (O(n |
(O(n |
במערך כללי: (O(n
במערך ממוין: (O(logn
|
| רשימה מקושרת |
(O(1 |
(O(1 ברשימה דו-כיוונית |
(O(n |
| Heap |
(O(logn |
(O(logn |
(O(n |
| עץ חיפוש בינארי |
(O(logn בממוצע
(O(n במקרה הגרוע |
(O(logn בממוצע
(O(n במקרה הגרוע |
(O(logn בממוצע
(O(n במקרה הגרוע |
| עץ אדום שחור |
(O(logn |
(O(logn |
(O(logn |
| Hash table סגור |
(O(1 בממוצע
(O(n במקרה הגרוע
|
(O(1 בממוצע
(O(n במקרה הגרוע |
(O(1 בממוצע
(O(n במקרה הגרוע |
| Hash table פתוח |
(O(1
|
(O(1 בממוצע
(O(logn במקרה הגרוע |
(O(1 בממוצע
(O(logn במקרה הגרוע |
מציאת איבר מינימלי:
ב- Heap ובמערך ממוין ניתן למצוא את האיבר המינימלי בזמן (O(1.
ב- Hash table הזמן הוא (O(n. בשאר מבני הנתונים הזמן למציאת איבר
מינימלי זהה לזמן של חיפוש איבר.
