Σε αυτό το σεμινάριο, θα μάθετε τι είναι το κύριο θεώρημα και πώς χρησιμοποιείται για την επίλυση των σχέσεων υποτροπής.
Η κύρια μέθοδος είναι ένας τύπος για την επίλυση των σχέσεων επανάληψης της φόρμας:
T (n) = aT (n / b) + f (n), όπου, n = μέγεθος εισόδου a = αριθμός υποπροβλημάτων στην αναδρομή n / b = μέγεθος κάθε υποπροβλήματος. Όλα τα υποπροβλήματα θεωρείται ότι έχουν το ίδιο μέγεθος. f (n) = κόστος της εργασίας που πραγματοποιείται εκτός της αναδρομικής κλήσης, το οποίο περιλαμβάνει το κόστος διαίρεσης του προβλήματος και το κόστος συγχώνευσης των λύσεων Εδώ, τα ≧ 1 και b> 1 είναι σταθερές και το f (n) είναι ασυμπτωτικά θετικό λειτουργία.
Μια ασυμπτωτικά θετική συνάρτηση σημαίνει ότι για μια αρκετά μεγάλη τιμή του n, έχουμε f(n)> 0.
Το κύριο θεώρημα χρησιμοποιείται για τον υπολογισμό της χρονικής πολυπλοκότητας των σχέσεων υποτροπής (αλγόριθμοι διαίρεσης και κατάκτησης) με απλό και γρήγορο τρόπο.
Κύριο Θεώρημα
Εάν a ≧ 1και b> 1είναι σταθερές και f(n)είναι ασυμπτωτικά θετική συνάρτηση, τότε η χρονική πολυπλοκότητα μιας αναδρομικής σχέσης δίνεται από
T (n) = aT (n / b) + f (n) όπου, T (n) έχει τα ακόλουθα ασυμπτωτικά όρια: 1. Εάν f (n) = O (n log b a-ϵ ), τότε T (n ) = Θ (n log b a ). 2. Εάν f (n) = Θ (n log b a ), τότε T (n) = Θ (n log b a * log n). 3. Εάν f (n) = Ω (n log b a + ϵ ), τότε T (n) = Θ (f (n)). ϵ> 0 είναι μια σταθερά.
Κάθε μία από τις παραπάνω προϋποθέσεις μπορεί να ερμηνευθεί ως:
- Εάν το κόστος επίλυσης των υπο-προβλημάτων σε κάθε επίπεδο αυξάνεται κατά έναν συγκεκριμένο παράγοντα, η τιμή του
f(n)θα γίνει πολυωνυμικά μικρότερη από . Έτσι, η πολυπλοκότητα του χρόνου καταπιέζεται από το κόστος του τελευταίου επιπέδου δηλαδή.nlogb anlogb a - Εάν το κόστος επίλυσης του υπο-προβλήματος σε κάθε επίπεδο είναι σχεδόν ίσο, τότε η τιμή του
f(n)θα είναι . Έτσι, η πολυπλοκότητα του χρόνου θα είναι φορές το συνολικό αριθμό των επιπέδων, δηλαδή.nlogb af(n)nlogb a * log n - Εάν το κόστος επίλυσης των υποπροβλημάτων σε κάθε επίπεδο μειωθεί κατά έναν συγκεκριμένο παράγοντα, η τιμή του
f(n)θα γίνει πολυωνυμικά μεγαλύτερη από . Έτσι, η πολυπλοκότητα του χρόνου καταπιέζεται από το κόστος .nlogb af(n)
Λύθηκε Παράδειγμα Κύριου Θεωρήματος
T (n) = 3T (n / 2) + n2 Εδώ, a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1.58 <2 δηλ. f (n) <n log b a + ϵ , όπου, ϵ είναι μια σταθερά. Η υπόθεση 3 υπονοεί εδώ. Έτσι, T (n) = f (n) = Θ (n 2 )
Περιορισμοί Master Theorem
Το κύριο θεώρημα δεν μπορεί να χρησιμοποιηθεί εάν:
- Το T (n) δεν είναι μονοτονικό. π.χ.
T(n) = sin n f(n)δεν είναι πολυώνυμο. π.χ.f(n) = 2n- a δεν είναι σταθερά. π.χ.
a = 2n a < 1
