Σε αυτό το σεμινάριο, θα μάθετε πώς λειτουργεί ο αλγόριθμος διαίρεσης και κατάκτησης. Θα συγκρίνουμε επίσης την προσέγγιση διαίρεσης και κατάκτησης έναντι άλλων προσεγγίσεων για την επίλυση ενός αναδρομικού προβλήματος.
Ένας αλγόριθμος διαίρεσης και κατάκτησης είναι μια στρατηγική επίλυσης ενός μεγάλου προβλήματος
- σπάζοντας το πρόβλημα σε μικρότερα δευτερεύοντα προβλήματα
- επίλυση των υπο-προβλημάτων, και
- συνδυάζοντάς τα για να λάβετε την επιθυμητή απόδοση.
Για να χρησιμοποιήσετε τον αλγόριθμο διαίρεσης και κατάκτησης, χρησιμοποιείται η αναδρομή . Μάθετε για την αναδρομή σε διαφορετικές γλώσσες προγραμματισμού:
- Επανάληψη στην Ιάβα
- Επανάληψη στην Python
- Επανάληψη σε C ++
Πώς λειτουργούν οι αλγόριθμοι διαίρεσης και κατάκτησης;
Ακολουθούν τα βήματα:
- Διαίρεση : Χωρίστε το δεδομένο πρόβλημα σε δευτερεύοντα προβλήματα χρησιμοποιώντας αναδρομή.
- Conquer : Λύστε τα μικρότερα δευτερεύοντα προβλήματα αναδρομικά. Εάν το υποπρόβλημα είναι αρκετά μικρό, τότε λύστε το απευθείας.
- Combine: Συνδυάστε τις λύσεις των υπο-προβλημάτων που αποτελούν μέρος της αναδρομικής διαδικασίας για την επίλυση του πραγματικού προβλήματος.
Ας κατανοήσουμε αυτήν την έννοια με τη βοήθεια ενός παραδείγματος.
Εδώ, θα ταξινομήσουμε έναν πίνακα χρησιμοποιώντας την προσέγγιση διαίρεσης και κατάκτησης (π.χ. ταξινόμηση συγχώνευσης).
- Αφήστε τον δεδομένο πίνακα να είναι:
Array για συγχώνευση - Χωρίστε τον πίνακα σε δύο μισά.
Χωρίστε τον πίνακα σε δύο τμήματα
Και πάλι, διαιρέστε κάθε τμήμα αναδρομικά σε δύο μισά έως ότου λάβετε μεμονωμένα στοιχεία.
Χωρίστε τον πίνακα σε μικρότερα τμήματα - Τώρα, συνδυάστε τα μεμονωμένα στοιχεία με ταξινομημένο τρόπο. Εδώ, κατακτήστε και συνδυάστε τα βήματα δίπλα-δίπλα.
Συνδυάστε τα τμήματα
Χρόνος πολυπλοκότητας
Η πολυπλοκότητα του αλγορίθμου διαίρεσης και κατάκτησης υπολογίζεται χρησιμοποιώντας το κύριο θεώρημα.
T (n) = aT (n / b) + f (n), όπου, n = μέγεθος εισόδου a = αριθμός υποπροβλημάτων στην αναδρομή n / b = μέγεθος κάθε υποπροβλήματος. Όλα τα υποπροβλήματα θεωρείται ότι έχουν το ίδιο μέγεθος. f (n) = κόστος της εργασίας που πραγματοποιήθηκε εκτός της αναδρομικής κλήσης, το οποίο περιλαμβάνει το κόστος διαίρεσης του προβλήματος και το κόστος συγχώνευσης των λύσεων
Ας πάρουμε ένα παράδειγμα για να βρούμε τη χρονική πολυπλοκότητα ενός αναδρομικού προβλήματος.
Για ένα είδος συγχώνευσης, η εξίσωση μπορεί να γραφτεί ως:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Πού, a = 2 (κάθε φορά, ένα πρόβλημα χωρίζεται σε 2 υποπροβλήματα) n / b = n / 2 (το μέγεθος κάθε δευτερεύοντος προβλήματος είναι το ήμισυ της εισόδου) f (n) = χρόνος που απαιτείται για τη διαίρεση του προβλήματος και συγχώνευση των υποπροβλημάτων T (n / 2) = O (n log n) (Για να το κατανοήσετε αυτό, το κύριο θεώρημα.) Τώρα, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Διαίρεση και κατάκτηση Vs Dynamic προσέγγιση
Η προσέγγιση διαίρεσης και κατάκτησης χωρίζει ένα πρόβλημα σε μικρότερα υποπροβλήματα. Αυτά τα υποπροβλήματα επιλύονται περαιτέρω αναδρομικά. Το αποτέλεσμα κάθε υποπροβλήματος δεν αποθηκεύεται για μελλοντική αναφορά, ενώ, σε μια δυναμική προσέγγιση, το αποτέλεσμα κάθε υποπροβλήματος αποθηκεύεται για μελλοντική αναφορά.
Χρησιμοποιήστε την προσέγγιση διαίρεσης και κατάκτησης όταν το ίδιο πρόβλημα δεν επιλύεται πολλές φορές. Χρησιμοποιήστε τη δυναμική προσέγγιση όταν το αποτέλεσμα ενός υποπροβλήματος πρόκειται να χρησιμοποιηθεί πολλές φορές στο μέλλον.
Ας το καταλάβουμε με ένα παράδειγμα. Ας υποθέσουμε ότι προσπαθούμε να βρούμε τη σειρά Fibonacci. Τότε,
Διαίρεση και κατάκτηση προσέγγιση:
fib (n) Εάν n <2, επιστροφή 1 άλλο, επιστροφή f (n - 1) + f (n -2)
Δυναμική προσέγγιση:
mem = () fib (n) If n in mem: return mem (n) else, If n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f επιστροφή f
Σε μια δυναμική προσέγγιση, το mem αποθηκεύει το αποτέλεσμα κάθε υποπροβλήματος.
Πλεονεκτήματα του αλγόριθμου Divide and Conquer
- Η πολυπλοκότητα για τον πολλαπλασιασμό δύο πινάκων με τη χρήση της αφελής μεθόδου είναι O (n 3 ), ενώ η προσέγγιση divide and winer (δηλ. Πολλαπλασιασμός μήτρας του Strassen) είναι O (n 2.8074 ). Αυτή η προσέγγιση απλοποιεί επίσης άλλα προβλήματα, όπως ο Πύργος του Ανόι.
- Αυτή η προσέγγιση είναι κατάλληλη για συστήματα πολλαπλής επεξεργασίας.
- Κάνει αποτελεσματική χρήση μνήμης cache.
Διαίρεση και κατάκτηση εφαρμογών
- Δυαδική αναζήτηση
- Συγχώνευση ταξινόμησης
- Γρήγορη ταξινόμηση
- Πολλαπλασιασμός Matrix του Strassen
- Αλγόριθμος Karatsuba
