Διαίρεση και κατάκτηση αλγορίθμου Σημασία: Εξηγείται με παραδείγματα

Τι είναι οι αλγόριθμοι διαίρεσης και κατάκτησης; (Και όχι, δεν είναι "Διαίρεση και Συμφωνία")

Το Divide and Conquer είναι ένα αλγοριθμικό παράδειγμα (μερικές φορές λανθασμένα ονομάζεται "Divide and Concur" - ένα αστείο και κατάλληλο όνομα), παρόμοιο με τον Άπληστο και Δυναμικό Προγραμματισμό. Ένας τυπικός αλγόριθμος Divide and Conquer επιλύει ένα πρόβλημα χρησιμοποιώντας τα ακόλουθα τρία βήματα.

  1. Διαίρεση : Διαχωρίστε το δεδομένο πρόβλημα σε υποπροβλήματα του ίδιου τύπου. Αυτό το βήμα περιλαμβάνει τη διάσπαση του προβλήματος σε μικρότερα δευτερεύοντα προβλήματα. Τα δευτερεύοντα προβλήματα πρέπει να αντιπροσωπεύουν μέρος του αρχικού προβλήματος. Αυτό το βήμα γενικά ακολουθεί μια αναδρομική προσέγγιση για να διαιρέσει το πρόβλημα έως ότου κανένα δευτερεύον πρόβλημα δεν μπορεί να διαιρεθεί περαιτέρω. Σε αυτό το στάδιο, τα υπο-προβλήματα γίνονται ατομικά στη φύση, αλλά εξακολουθούν να αντιπροσωπεύουν μέρος του πραγματικού προβλήματος.
  2. Conquer : Επιλύστε αναδρομικά αυτά τα δευτερεύοντα προβλήματα. Αυτό το βήμα λαμβάνει πολλά μικρότερα δευτερεύοντα προβλήματα προς επίλυση. Γενικά, σε αυτό το επίπεδο, τα προβλήματα θεωρούνται «επιλυμένα» από μόνα τους.
  3. Combine : Συνδυάστε κατάλληλα τις απαντήσεις. Όταν επιλυθούν τα μικρότερα δευτερεύοντα προβλήματα, αυτό το στάδιο τα συνδυάζει αναδρομικά μέχρι να διαμορφώσουν μια λύση του αρχικού προβλήματος. Αυτή η αλγοριθμική προσέγγιση λειτουργεί αναδρομικά και τα βήματα κατάκτησης και συγχώνευσης λειτουργούν τόσο κοντά που εμφανίζονται ως ένα.

Αυτή η μέθοδος συνήθως μας επιτρέπει να μειώσουμε την πολυπλοκότητα του χρόνου σε μεγάλο βαθμό.

Για παράδειγμα, το Bubble Sort χρησιμοποιεί μια πολυπλοκότητα O(n^2), ενώ το quicksort (μια εφαρμογή Of Divide And Conquer) μειώνει την πολυπλοκότητα του χρόνου σε O(nlog(n)). Η Γραμμική Αναζήτηση έχει πολυπλοκότητα χρόνου O(n), ενώ η Δυαδική Αναζήτηση (μια εφαρμογή Διαίρεση και Κατακράτηση) μειώνει την πολυπλοκότητα του χρόνου σε O(log(n)).

Ακολουθούν ορισμένοι τυπικοί αλγόριθμοι που έχουν την ποικιλία αλγορίθμων Divide and Conquer.

Η δυαδική αναζήτηση  είναι ένας αλγόριθμος αναζήτησης. Σε κάθε βήμα, ο αλγόριθμος συγκρίνει το στοιχείο εισόδου (x) με την τιμή του μεσαίου στοιχείου σε πίνακα. Εάν οι τιμές ταιριάζουν, επιστρέψτε το δείκτη του μέσου. Διαφορετικά, εάν το x είναι μικρότερο από το μεσαίο στοιχείο, τότε ο αλγόριθμος επαναλαμβάνεται στην αριστερή πλευρά του μεσαίου στοιχείου, αλλιώς επαναλαμβάνεται στη δεξιά πλευρά του μεσαίου στοιχείου.

Το Quicksort  είναι ένας αλγόριθμος ταξινόμησης. Ο αλγόριθμος επιλέγει ένα στοιχείο περιστροφής, αναδιατάσσει τα στοιχεία συστοιχίας με τέτοιο τρόπο ώστε όλα τα στοιχεία μικρότερα από το επιλεγμένο στοιχείο περιστροφής να μετακινούνται στην αριστερή πλευρά του περιστρεφόμενου και όλα τα μεγαλύτερα στοιχεία μετακινούνται προς τη δεξιά πλευρά. Τέλος, ο αλγόριθμος ταξινομεί αναδρομικά τις δευτερεύουσες σειρές αριστερά και δεξιά του περιστρεφόμενου στοιχείου.

Το Merge Sort  είναι επίσης ένας αλγόριθμος ταξινόμησης. Ο αλγόριθμος χωρίζει τον πίνακα σε δύο μισά, τα ταξινομεί αναδρομικά και τελικά συγχωνεύει τα δύο ταξινομημένα μισά. Η χρονική πολυπλοκότητα αυτού του αλγορίθμου είναι O(nLogn), στην καλύτερη περίπτωση, στη μέση περίπτωση ή στη χειρότερη περίπτωση. Ήρθε η ώρα πολυπλοκότητα μπορεί εύκολα να γίνει κατανοητό από τους ισούται δε υποτροπής σε: T(n) = 2T(n/2) + n.

Πλησιέστερο ζεύγος πόντων  Το πρόβλημα είναι να βρείτε το πλησιέστερο ζεύγος πόντων σε ένα σύνολο σημείων στο επίπεδο xy. Το πρόβλημα μπορεί να λυθεί O(n^2)εγκαίρως υπολογίζοντας τις αποστάσεις κάθε ζεύγους σημείων και συγκρίνοντας τις αποστάσεις για να βρούμε το ελάχιστο. Ο αλγόριθμος Divide and Conquer λύνει το πρόβλημα O(nLogn)εγκαίρως.

Ο αλγόριθμος του Strassen  είναι ένας αποτελεσματικός αλγόριθμος για τον πολλαπλασιασμό δύο πινάκων. Μια απλή μέθοδος πολλαπλασιασμού δύο πινάκων χρειάζεται 3 ένθετους βρόχους και είναι O(n^3). Ο αλγόριθμος του Strassen πολλαπλασιάζει δύο πίνακες στο O(n^2.8974)χρόνο.

Ο αλγόριθμος Cooley – Tukey Fast Fourier Transform (FFT)  είναι ο πιο κοινός αλγόριθμος για το FFT. Είναι ένας αλγόριθμος διαίρεσης και κατάκτησης που λειτουργεί στο O(nlogn)χρόνο.

Ο αλγόριθμος Karatsuba  ήταν ο πρώτος αλγόριθμος πολλαπλασιασμού ασυμπτωτικά πιο γρήγορος από τον τετραγωνικό αλγόριθμο «σχολικής τάξης». Μειώνει τον πολλαπλασιασμό δύο n-ψηφίων αριθμών έως n ^ 1.585 (που είναι προσέγγιση του log του 3 στη βάση 2) ​​μονοψήφια προϊόντα. Επομένως, είναι ταχύτερος από τον κλασικό αλγόριθμο, ο οποίος απαιτεί n ^ 2 μονοψήφια προϊόντα.

Divide and Conquer (D & C) έναντι Dynamic Programming (DP)

Και τα δύο παραδείγματα (D & C και DP) χωρίζουν το δεδομένο πρόβλημα σε υποπροβλήματα και επιλύουν υποπροβλήματα. Πώς να επιλέξετε ένα από αυτά για ένα συγκεκριμένο πρόβλημα; Το Divide and Conquer πρέπει να χρησιμοποιείται όταν τα ίδια υποπροβλήματα δεν αξιολογούνται πολλές φορές. Διαφορετικά, θα πρέπει να χρησιμοποιείται δυναμικός προγραμματισμός ή απομνημόνευση.

Για παράδειγμα, το Binary Search είναι ένας αλγόριθμος Divide and Conquer, δεν αξιολογούμε ποτέ ξανά τα ίδια υποπροβλήματα. Από την άλλη πλευρά, για τον υπολογισμό του nth Fibonacci number, Dynamic Programming θα πρέπει να προτιμάται.