Master theorem dell'analisi degli algoritmi

In analisi degli algoritmi, il master theorem, che è un caso particolare del teorema di Akra-Bazzi, fornisce una ricetta per caratterizzare in termini di analisi asintotica le funzioni definite mediante relazioni di ricorrenza dei tipi che si incontrano spesso nella pratica.

Sia data una relazione della forma

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

Con: a = è il numero di sottoproblemi della ricorsione, 1/b = la porzione del problema originale rappresentato in ogni sottoproblema, f(n) = la funzione di costo, che include la suddivisione del problema e la ricostruzione della soluzione.

Inoltre $a \ge 1\,$ e $b > 1\,$ si considerano costanti e $\;\frac{n}{b}\;$ si può interpretare sia come $\;\left\lfloor \frac{n}{b} \right\rfloor\;$ (funzione pavimento), sia come $\;\left\lceil \frac{n}{b} \right\rceil\;$ (funzione soffitto) del rapporto $\;\frac{n}{b}.$

Si trova che si possono stabilire delle limitazioni per la funzione $\,T(n)\,$ in corrispondenza di una delle situazioni che seguono.

Caso 1: Se $\quad f(n) \in O\left( n^{\log_b a - \varepsilon} \right)$ (notazione O grande) per qualche costante $\quad \varepsilon > 0\,$

allora $\quad T(n) \in \Theta\left( n^{\log_b a} \right).\,$

Caso 2: Se $\quad f(n) \in \Theta\left( n^{\log_b a} \right)\,$

allora $\quad T(n) \in \Theta\left( n^{\log_b a} \log(n)\right).\,$

Case 3: Se $\quad f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right)\;$ per qualche costante $\quad \varepsilon > 0\,$

e se $\quad a f\left( \frac{n}{b} \right) \le c f(n)\;$ per qualche costante $\; c < 1\;$ e per qualche n sufficientemente elevato,

allora $\quad T(n) \in \Theta(f(n)).$

Voci correlate

Master theorem di MacMahon

Analisi asintotica

Master-Theorem | Master theorem | שיטת האב | Master theorem

Gourt Home::Gourt :: Master theorem dell'analisi degli algoritmi

Voci correlate