אלגוריתם חיפוש – הבדלי גרסאות
תיקון סטייה |
כוח גס הוא חיפוש ממצה בסיסי |
||
| שורה 1: | שורה 1: | ||
ב[[מדעי המחשב]], '''אלגוריתם חיפוש''' הוא [[אלגוריתם]] המשמש לחיפוש נתון נדרש ב[[מבנה נתונים]]. חיפוש הוא פעולה בסיסית בפיתוח [[תוכנה]], למשל לשם אחזור מידע מ[[בסיס נתונים]], ולכן הושקע מאמץ בפיתוח אלגוריתמים יעילים לביצוע משימה זו. |
ב[[מדעי המחשב]], '''אלגוריתם חיפוש''' הוא [[אלגוריתם]] המשמש לחיפוש נתון נדרש ב[[מבנה נתונים]]. חיפוש הוא פעולה בסיסית בפיתוח [[תוכנה]], למשל לשם אחזור מידע מ[[בסיס נתונים]], ולכן הושקע מאמץ בפיתוח אלגוריתמים יעילים לביצוע משימה זו. |
||
החיפוש הבסיסי ביותר הוא חיפוש ב[[כוח גס]] - מעבר על כל הנתונים לפי סדרם, עד למציאת הנתון המבוקש. זהו חיפוש בלתי יעיל, וכאשר מספר הנתונים שבהם יש לחפש הוא גדול, החיפוש נמשך זמן רב, במידה בלתי סבירה. |
החיפוש הבסיסי ביותר הוא חיפוש ב[[כוח גס]] - מעבר על כל הנתונים לפי סדרם, עד למציאת הנתון המבוקש, אם הוא אכן נמצא. מקובל לכנותו חיפוש ממצה בסיסי, או אלגוריתם חיפוש נאיבי. זהו חיפוש בלתי יעיל, וכאשר מספר הנתונים שבהם יש לחפש הוא גדול, החיפוש נמשך זמן רב, במידה בלתי סבירה. |
||
כאשר הנתונים ממוינים, ניתן לשפר משמעותית את החיפוש על ידי שימוש ב[[חיפוש בינארי]]. הבעיתיות בשיטה זו היא הדרישה שהנתונים יהיו ממוינים מראש, והצורך לשוב ולמיינם בכל פעם שנתון חדש מוכנס למאגר או כשנתון קיים מוצא ממנו. |
כאשר הנתונים ממוינים, ניתן לשפר משמעותית את החיפוש על ידי שימוש ב[[חיפוש בינארי]]. הבעיתיות בשיטה זו היא הדרישה שהנתונים יהיו ממוינים מראש, והצורך לשוב ולמיינם בכל פעם שנתון חדש מוכנס למאגר או כשנתון קיים מוצא ממנו. |
||
גרסה מ־16:09, 8 באפריל 2015
במדעי המחשב, אלגוריתם חיפוש הוא אלגוריתם המשמש לחיפוש נתון נדרש במבנה נתונים. חיפוש הוא פעולה בסיסית בפיתוח תוכנה, למשל לשם אחזור מידע מבסיס נתונים, ולכן הושקע מאמץ בפיתוח אלגוריתמים יעילים לביצוע משימה זו.
החיפוש הבסיסי ביותר הוא חיפוש בכוח גס - מעבר על כל הנתונים לפי סדרם, עד למציאת הנתון המבוקש, אם הוא אכן נמצא. מקובל לכנותו חיפוש ממצה בסיסי, או אלגוריתם חיפוש נאיבי. זהו חיפוש בלתי יעיל, וכאשר מספר הנתונים שבהם יש לחפש הוא גדול, החיפוש נמשך זמן רב, במידה בלתי סבירה.
כאשר הנתונים ממוינים, ניתן לשפר משמעותית את החיפוש על ידי שימוש בחיפוש בינארי. הבעיתיות בשיטה זו היא הדרישה שהנתונים יהיו ממוינים מראש, והצורך לשוב ולמיינם בכל פעם שנתון חדש מוכנס למאגר או כשנתון קיים מוצא ממנו.
כדי לאפשר חיפוש מהיר מחד, ולהימנע מן הצורך למיין את הנתונים בכל פעם שחל בהם שינוי מאידך, פותחו מבני נתונים השומרים על הנתונים במצב ממוין.
מבנה נתונים בסיסי המאפשר זאת הוא עץ חיפוש, שהוא מבנה נתונים ממוין המאפשר הכנסה, הוצאה וחיפוש. עצי חיפוש משוכללים יותר כמו עץ אדום שחור ועץ AVL מאפשרים לבצע את הפעולות הללו במהירות (דהינו בסיבוכיות נמוכה).
לחיפוש בגרפים (כמו עצי החיפוש שהוזכרו לעיל) משמשים אלגוריתם חיפוש לעומק ואלגוריתם חיפוש לרוחב.
לקריאה נוספת
- דונלד קנות', Sorting and Searching, כרך 3 בסדרה The Art of Computer Programming.
