הפרד ומשול - האסטרטגיה שמאחורי האלגוריתמים המהירים

הפרד ומשול (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).