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

Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. Βοηθήστε συνδέοντας το κείμενο με τις πηγές χρησιμοποιώντας παραπομπές, ώστε να είναι επαληθεύσιμο. Το πρότυπο τοποθετήθηκε χωρίς ημερομηνία. Για τη σημερινή ημερομηνία χρησιμοποιήστε: {χωρίς παραπομπές|28|02|2024}

Αυτό το λήμμα είναι ορφανό καθώς λίγα ή και καθόλου λήμματα συνδέουν σε αυτό. Παρακαλούμε βοηθήστε βάζοντας συνδέσμους προς αυτό σε λήμματα για σχετικά θέματα. (Φεβρουαρίου 2010)

Το μάστερ θεώρημα (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}$ καθορίζει την λύση της εξίσωσης.