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

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

Γενική Μορφή

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

$T(n)=a\cdot T\left(\frac{n}{b}\right)+f(n)$

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

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

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

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

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

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

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

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

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

Συμπέρασμα

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

Πρότυπο:Μαθηματικά-επέκταση