Master theorem
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Tο Master theorem είναι ειδική περίπτωση του θεωρήματος Akra-Bazzi. Χρησιμοποιείται στην ανάλυση αλγορίθμων για τον προσδιορισμό του ασυμπτωτικού ορίου μιας αναδρομικής συνάρτησης. Παρ'ολα αυτά δεν επιλύεται κάθε αναδρομική σχέση με το Master theorem.
[Επεξεργασία] Γενική Μορφή
Η γενική μορφή του Master Theorem είναι:
Όπου T(n)είναι η αναδρομική σχέση, a και b είναι σταθερές και f(n) είναι μια μη αρνητική συνάρτηση ανεξάρτητη της T(n)
Για να εφαρμοστεί το Master Theorem θα πρέπει να ισχύει για τις δυο σταθερές: a ≥ 1 και b > 1
Το Master Theorem χωρίζεται σε 3 περιπτώσεις, οι οποίες μπορούν συνήθως να δώσουν λύση. Παρόλα αυτά υπάρχει και μια ειδική περίπτωση, η οποία μπορεί να χρησιμοποιηθεί όταν δεν ταιριάζουν όλες οι άλλες.