Μάστερ Θεώρημα

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

Tο μάστερ θεώρημα (master theorem) είναι ειδική περίπτωση του θεωρήματος Akra-Bazzi. Χρησιμοποιείται στην ανάλυση αλγορίθμων για τον προσδιορισμό του ασυμπτωτικού ορίου μιας αναδρομικής συνάρτησης. Ωστόσο δεν επιλύεται κάθε αναδρομική σχέση με το μάστερ θεώρημα.

Γενική Μορφή[Επεξεργασία | επεξεργασία κώδικα]

Η γενική μορφή του θεωρήματος είναι:

T(n) = a \sdot T(\textstyle \frac{n}{b}) + f(n)

Όπου T(n)είναι η αναδρομική σχέση, a και b είναι σταθερές και f(n) είναι μια μη αρνητική συνάρτηση ανεξάρτητη της T(n)

Για να εφαρμοστεί το μάστερ θεώρημα θα πρέπει να ισχύει για τις δυο σταθερές: a ≥ 1  και  b > 1

Το μάστερ θεώρημα χωρίζεται σε τρεις περιπτώσεις, οι οποίες μπορούν συνήθως να δώσουν λύση. Παρόλα αυτά υπάρχει και μια ειδική περίπτωση, η οποία μπορεί να χρησιμοποιηθεί όταν δεν ταιριάζουν όλες οι άλλες.

- Αν f(n) = O(n^{ {log}_{b}a } )

, τότε T(n)= \Theta (n^{ {log}_{b}a } )
[Επεξεργασία | επεξεργασία κώδικα]

-Αν f(n) = \Theta(n^{ {log}_{b}a } )
, τότε T(n)= \Theta (n^{ {log}_{b}a }\sdot logn )
[Επεξεργασία | επεξεργασία κώδικα]

-Αν f(n) = \Omega(n^{ {log}_{b}a } )
και af(n/b)<f(n)
, τότε T(n)= \Theta (f(n)
)
[Επεξεργασία | επεξεργασία κώδικα]

Δηλαδή ο ασυμπτωτικά μεγαλύτερος απο τους όρους f(n)

και n^{ {log}_{b}a }
καθορίζει την λύση της εξίσωσης.