המ.. ננסה קצת...
AVL: כעקרון היתרון האדיר של המבנה הזה הוא בכך שלמרות שהוא תופס בדיוק את כמות הזיכרון המינימאלית הדרושה להחזיק את הנתונים שלך הוא מאפשר את כל הפעולות על המילון בסיבוכיות לוגוריתמית בכמות הנתונים במבנה. אתה מוסיף סדר גודל של עוד 12-16 בתים של זיכרון לכל נתון (גודל זניח לכל הדעות) ובתמורה מקבל חיפוש מאד יעיל. עצי B: כעקרון, מדובר במבנה שדומה לעץ AVL, חוץ מהעובדה שהנתונים נשמרים רק בעלים. עצי B יכולים להיות בגדלים משתנים של בנים לעומת המבנה הפשוט של עץ בינארי מה שעלול קצת לסבך אותם, אבל הם יעילים מאד כשאתה מחפש נתונים בכונן עם גישות איטיות, שכן כשאתה קורא בלוקים מהדיסק הקשיח שלך אתה קורא בלוק שיכול להכיל את רב העץ חוץ מהבנים ומהר מאד למצא את הבלוק שבו נשמר המידע ממש. Heap: כמבנה המממש מילון אני לא רואה בו יתרון גדול... היתרון שלו הוא בעובדה שניתן להפוך כל מערך ל-heap בזמן ליניארי. מהרגע שאתה עושה את זה, יש לך גישה לכל איבר ב-(O(1 (בתנאי שאתה יודע לאן אתה ניגש) ומציאת מינימום\מקסימום מאד מהירים. Skip List: כמו עץ AVL, אבל ע"י תוספת זיכרון סבירה אתה יכול להגיע לביצועים הדומים לעץ AVL תוך שימוש באלגוריתמים הפשוטים בהרבה לצרכי מחיקה והוספה (אלגוריתם הטלת מטבע, למשל) hash table: במילה אחת: חיפוש. טבלת ערבול\גיבוב מאפשרת לך גישה לנתונים בזמן קבוע בממוצע. כלומר גם טבלה המכילה מליוני רשומות תאפשר לך גישה לרשומה בזמן קצר למדי שלא ישתנה כתוצאה מהוספה של כמות נתונים סבירה. החסרון הבולט - שימוש בגודל מבנה קבוע - ניתן לפיצוי ע"י פעולות rehash ופעולות הגדלה שעדין יתנו לך זמן עבודה משוערך קבוע. כלומר, לא משנה מה אתה עושה פה, בסופו של דבר זה מבנה נתונים שמהיר מאד מצד אחד, ופשוט למימוש מצד שני. החיסרון הגדול: אם יש לך נתונים שאין עבורם ערבול סביר, ערבול שעולה המון (לדוגמא קבצים גדולים) וטעות בקביעת גודל הטבלה (כאשר כמות הנתונים מגדילה את פקטור העומס לגודל לא סביר). רב הדברים פתירים באופן כזה או אחר, אבל ישנם מצבים שבהם מבנים דינאמיים עדיפים. DFS ו-BFS הם אלגוריתמים למעבר על גרף... BFS מחשב מסלולים קצרים ביותר מצומת S לכל צומת אחר ובונה עץ של המסלולים הקצרים. חסרון: לא נותן מידע על צמתים שאינם ברכיב הקשירות של צומת המקור. DFS מחשב רכיבי קשירות של גרף. אחלה אם אתה רוצה לראות מאיזה צומת אפשר להגיע לאיזה צומת אחר, סה"כ נותן לך מידע לגבי זמני גילוי. הבעיה הגדולה היא שהפלט יכול להשתנות מהרצה להרצה בתלות בצומת המקור.. יש לו שימושים כחלק מאלגוריתמים אחרים כמו מיון טופולוגי, תזמון תהליכים תלויים וכו' מיונים: heapSort: יתרון ענקי: לא צורך זיכרון נוסף. יש לך מערך - אתה מקבל את הערימה שלך כבר באותו המערך. אם אתה בסה"כ מחפש מספר איברים מקסימליים\מינימאליים הוא מאד יעיל. כל מני וריאציות יכולות לאפשר לך לנצל את העיקרון כדי לקבל מידע רחב יותר (חפש על ערימות min-max, למשל). Radix: אלגוריתם יעיל מאד למיון. נותן לך מיון בזמן ליניארי. כמובן שזה מגיע בהתניה מסויימת על הקלט שלך. אם לצורך העניין יש לך מערך של מספרים שלמים בגודל עד מיליארד (10 ספרות) תקבל מיון יעיל למדי [הגיוני, int חסום ב-4 מיליארד]... BucketSort: אלגוריתם מיון יעיל בסה"כ, אבל רק בתנאי שטווח הערכים שלך הוא לא יותר מדי גדול... הבעיה היא שזה מצריך ידע מוקדם על הקלט.. היתרון הוא שהוא מאד פשוט למימוש.... ובמידה רבה יעיל יותר מה-radix. counting: אם אני זוכר נכון, זה אלגוריתם שעובד כמעט בדיוק כמו bucket, אבל אני לא לחלוטין זוכר... בכל מקרה, נסה לחשוב קצת לבד.. מקווה שקצת עזרתי...
