חיפוש רקורסיבי וסינון
הוצג| English | משמעות |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | חלק-וגדול-פתרון |
| merge sort/mɜːdʒ sɔːt/ | מיון מיזוג |
| merge/mɜːdʒ/ | מיזוג |
רקורסיה פוגשת חיפוש ומיון
- אותו רעיון של פירוק ושליטה (divide-and-conquer) מאפשר את החיפוש הבינארי הרקורסיבי ואת מיון האיחוד (merge sort).
- לחלקו את הבעיה לשני חלקים, לפתור את החלקים, ולאחד.
- חיפוש בינארי רקורסיבי מחפש בחצי אחד על ידי הקראת עצמו אליו.
- מיון איחוד מיין כל חצי, ולאחר מכן מאחד את החציים הממוינים יחד.
חיפוש בינארי רקורסיבי
- מקרה בסיסי: טווח ריק אומר שהמטרה לא נמצאה.
- הסתכלו על האלמנט אמצעי. אם זהו המטרה, החזירו את המקדם שלו.
- אם המטרה קטנה יותר, התקשרו בחצי השמאלי; אם גדולה יותר, בחצי הימני.
- כל שימוש מחלק את הטווח לחצי — אותו
O(log n), כתוב בצורה רקורסיבית.
מיון איחוד
- פצלו את המערך לשני חצאים; מיינו כל חצי רקורסיבית.
- מקרה בסיסי: מערך בעל 0 או 1 אלמנט הוא כבר במיון.
- מיזוג: סורגו את שני החצאים הממוינים, תמיד על ידי בחירת האלמנט הקטן ביותר מראש.
- מהיר משמעותית מסיוני
n²— כ-n log nעבודה.
מדוע גישת חלק-וקח-פותר מנצחת
- חלוקה של הבעיה למחצה בכל שלב נותנת את גורם ה-
log n. - ה-
n log nשל מיזוג-סידור (merge sort) עולה על ה-n²של סיון בחירה/הכנסה במערות גדולות. - המקרה הבסיסי (מערך ריק או אלמנט אחד) מעצור כל ענף.
- אותו צורה כמו בכל רקורסיה: פיצול למטה, שילוב חזרה למעלה.
חיפוש בינארי רקורסיבי מתקיים רק על חצי אחד (היעד נמצא רק בצד אחד); מיזוג-סידור מתקיים על שני החצאים ואז מאחד אותם. שניהם זקוקים למקרה בסיסי — טווח ריק פירושו "לא נמצא" לחיפוש; מערך בעל 0 או 1 אלמנטים הוא כבר ממוין עבור מיזוג-סידור. גישת חלק-וקח-פותר היא מה שהופכת אותם למהירים (O(log n) ו-O(n log n)).
מיזוג-סידור של [3, 1, 2, 4]:
- פיצול ל-
[3, 1]ול-[2, 4]; סידור כל אחד →[1, 3]ו-[2, 4]. - מיזוג: לקיחת 1, אחר כך 2, אחר כך 3, אחר כך 4 →
[1, 2, 3, 4]. - בכל מיזוג נבחר האלמנט הקטן ביותר מראש בתור.
חיפוש בינארי רקורסיבי מתקיים על חצי אחד (מקרה בסיסי: טווח ריק = לא נמצא) עבור חיפוש O(log n). מיזוג-סידור מתקיים על שני החצאים ומאחד אותם (מקרה בסיסי: 0 או 1 אלמנט) לסידור O(n log n). שניהם חלק-וקח-פותר: פיצול למטה, שילוב חזרה למעלה — הרבה מהירים יותר מ-n².
מיזוג מחלק לשני חצאים, ולאחר מכן מאחד כלפי מעלה
אלמנטים יחידים מסודרים (מקרה בסיס); מיזוג משלב אותם כלפי מעלה.
חיפוש בינארי רקורסיבי מבצע ריקורסיה על...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
היעד נמצא רק בצד אחד מהאמצע.
מיזוג מבצע ריקורסיה על...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
לסדר כל חצי, ולאחר מכן למזג את שני החצאים המסודרים.
המקרה הבסיסי למיזוג הוא מערך של...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
אלמנט אחד (או אפס) אינו זקוק לסידור.
זמן הריצה של מיון איחוד הוא כ-…
Difficulty 1/5 · 100 coins + a small bonus on first completion today
⟦log n⟧ רמות חלוקה, עבודה של ⟨⟩ n בכל רמה.
גם חיפוש בינארי רקורסיבי וגם מיון איחוד הם אלגוריתמים סוגר-כבש-עשה.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
שניהם מחלקים את הבעיה לשני חלקים ומתקשרים רקורסיבית.
סדרו את שלב האיחוד עבור החצאים [1,3] ו-[2,4].
Difficulty 3/5 · 200 coins + a small bonus on first completion today
תמיד קחו את האלמנט הקטן ביותר בחזית: 1, 2, 3, 4.