הפרד ומשול - האסטרטגיה שמאחורי האלגוריתמים המהירים
העיקרון של חלוקה לתת-בעיות, פתרון רקורסיבי ומיזוג - הבסיס ל-Merge Sort, Quick Sort ועוד.
הפרד ומשול (Divide and Conquer) היא פרדיגמה אלגוריתמית בת שלושה שלבים: לחלק את הבעיה לתת-בעיות קטנות יותר, לפתור אותן רקורסיבית, ולשלב את הפתרונות. זה הבסיס לאלגוריתמים המהירים ביותר עבור בעיות רבות.
שלושת השלבים
- Divide - חלקו את הקלט לשני (או יותר) חלקים בערך שווים
- Conquer - פתרו כל חלק רקורסיבית. כשהוא קטן מספיק (מקרה בסיס), פתרו ישירות
- Combine - שלבו את הפתרונות החלקיים לפתרון של הבעיה המקורית
דוגמאות קלאסיות
- Merge Sort - חלוקה לשני חצאים, מיון רקורסיבי, מיזוג ב-O(n)
- Quick Sort - חלוקה לפי ציר, מיון רקורסיבי לכל צד
- Binary Search - חלוקה לחצי בכל שלב - O(log n)
- כפל מטריצות של Strassen - O(n^2.81) במקום O(n³)
- Closest Pair of Points - מציאת זוג הנקודות הקרוב ביותר ב-O(n log n)
Master Theorem - נוסחה לסיבוכיות
עבור רקורסיה מהצורה T(n) = aT(n/b) + f(n), Master Theorem נותן פתרון מהיר. למשל ב-Merge Sort: T(n) = 2T(n/2) + O(n) → O(n log n). ב-Binary Search: T(n) = T(n/2) + O(1) → O(log n).
הפרד ומשול בולט במיוחד בעיבוד מקבילי - תת-הבעיות בלתי-תלויות ויכולות לרוץ במקביל על מעבדים שונים, מה שמאיץ דרמטית את הביצועים.
מתי לא להשתמש?
אם תת-הבעיות חופפות (אותה תת-בעיה מחושבת שוב ושוב), הפרד ומשול נאיבי יהיה איטי בהרבה מ-DP. למשל, חישוב פיבונאצ'י רקורסיבי הוא 'הפרד ומשול' אקספוננציאלי - DP פותר אותו ב-O(n).
שאלות נפוצות
מהם שלושת השלבים של הפרד ומשול?
חלוקה — פיצול הבעיה לתת-בעיות קטנות יותר מאותו סוג; שליטה — פתרון כל תת-בעיה רקורסיבית, עד למקרה בסיס שנפתר ישירות; ומיזוג — צירוף הפתרונות החלקיים לפתרון הבעיה המקורית. במיון מיזוג, למשל, החלוקה היא לשני חצאים והמיזוג הוא איחוד שתי רשימות ממוינות.
מה ההבדל בין הפרד ומשול לתכנון דינמי?
בשתי הגישות מפרקים בעיה לתת-בעיות, אבל בהפרד ומשול התת-בעיות זרות ואינן חופפות, ולכן אין טעם לשמור תוצאות. בתכנון דינמי התת-בעיות חופפות וחוזרות שוב ושוב, ולכן שמירת התוצאות בטבלה היא בדיוק מה שחוסך את הזמן האקספוננציאלי.
מהי משפט המאסטר ולמה הוא שימושי?
משפט המאסטר הוא כלל שמאפשר לפתור נוסחאות נסיגה מהצורה T(n) = a·T(n/b) + f(n) ולקבל את הסיבוכיות ישירות, בלי לפרוש את עץ הרקורסיה. הוא משווה את קצב הגידול של f(n) לזה של n^(log_b a) ובוחר את הדומיננטי. עבור מיון מיזוג, שבו a=2, b=2 ו-f(n)=O(n), הוא נותן O(n log n).