Divide and conquer επιλύει ένα πρόβλημα με (1) διαίρεση του σε μικρότερα υποπροβλήματα, (2) κατάκτηση κάθε υποπροβλήματος αναδρομικά, και (3) συνδυασμό των αποτελεσμάτων. Πολλοί αποδοτικοί αλγόριθμοι ακολουθούν αυτό το πρότυπο.
Αν τα υποπροβλήματα είναι ανεξάρτητα και μειώνονται γρήγορα, το συνολικό έργο ακολουθεί μια αναδρομική σχέση που μπορείς να αναλύσεις με το .
def max_dc(arr, lo, hi):
if lo == hi: # base case: one element
return arr[lo]
mid = (lo + hi) // 2
left = max_dc(arr, lo, mid) # conquer left
right = max_dc(arr, mid + 1, hi) # conquer right
return max(left, right) # combine
max_dc([3, 9, 2, 7], 0, 3) # -> 9
Συχνά T(n) = a·T(n/b) + f(n); για merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Χρησιμοποίησε όταν ένα πρόβλημα χωρίζεται καθαρά σε ανεξάρτητα υποπροβλήματα. Αν τα υποπροβλήματα επικαλύπτονται, προτίμησε dynamic programming αντ' αυτού (για αποφυγή επανυπολογισμού). Το overhead αναδρομής και το βήμα συνδυασμού μπορούν να κυριαρχήσουν για μικρές εισόδους.
Το divide and conquer είναι ένα επαναχρησιμοποιούμενο σχέδιο πίσω από μια τεράστια κλάση αποδοτικών αλγορίθμων.
Η αναγνώριση του προτύπου σας επιτρέπει να παράγετε και να αναλύσετε νέους αλγόριθμους γρήγορα με αναδρομικές σχέσεις.
Επίσης, αντιστοιχίζεται φυσικά στον παραλληλισμό, καθώς τα ανεξάρτητα υποπροβλήματα μπορούν να εκτελεστούν ταυτόχρονα.