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

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

Γενική Μορφή

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

${\displaystyle T(n)=a\cdot T{\bigg (}{\frac {n}{b}}{\bigg )}+f(n)}$

,όπου ${\displaystyle T(n)}$ είναι η αναδρομική σχέση, ${\displaystyle a}$ και ${\displaystyle b}$ είναι σταθερές και ${\displaystyle f(n)}$ είναι μια μη αρνητική συνάρτηση ανεξάρτητη της ${\displaystyle T(n)}$.

Για να εφαρμοστεί το μάστερ θεώρημα θα πρέπει να ισχύουν για τις δυο σταθερές ${\displaystyle a,b}$ οι εξής ανισότητες: ${\displaystyle a\geq 1}$ και ${\displaystyle b\geq 1}$.

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

Περίπτωση πρώτη

Αν ${\displaystyle f(n)=O(n^{{log}_{b}a})}$, τότε ${\displaystyle T(n)=\Theta (n^{{log}_{b}a}).}$

Περίπτωση δεύτερη

Αν ${\displaystyle f(n)=\Theta (n^{{log}_{b}a})}$, τότε ${\displaystyle T(n)=\Theta (n^{{log}_{b}a}\cdot logn).}$

Περίπτωση τρίτη

Αν ${\displaystyle f(n)=\Omega (n^{{log}_{b}a})}$ και ${\displaystyle af(n/b)<cf(n),c={\text{σταθ.}}}$, τότε ${\displaystyle T(n)=\Theta (f(n)).}$

Συμπέρασμα

Δηλαδή, ο ασυμπτωτικά μεγαλύτερος απο τους όρους ${\displaystyle f(n)}$ και ${\displaystyle n^{{log}_{b}a}}$ καθορίζει την λύση της εξίσωσης.