In questo articolo riguardante gli algoritmi, vedremo a che serve e come usare il Teorema Master.

Il Teorema Master (o conosciuto anche come teorema dell’esperto o teorema principale) viene utilizzato nello studio di algoritmi per valutare il tempo di esecuzione di algoritmi ricorsivi che sfruttano il concetto di divide et impera.

Divide Et Impera è un motto latino che viene utilizzato di solito in campo politico: in informatica invece, con questo intendiamo la suddivisione di un problema in n sottoproblemi di dimensione [latex]n/b[/latex], la risoluzione ricorsiva di questi problemi più semplici e una ricombinazione di tutte le chiamate effettuate.

Ad esempio, l’equazione di ricorrenza per l’algoritmo di ordinamento MergeSort è:

[latex]T(n) = 2T(n/2) + \Theta (n)[/latex]

In questo caso è parecchio evidente come il tempo di esecuzione è diviso in due componenti dall’operazione di addizione:

  • la prima parte esegue la suddivisione in [latex]n/b[/latex] sottosequenze, ed in questo caso [latex]b=2[/latex],
  • la seconda la ricombinazione, ovvero il tempo di esecuzione di [latex]f(n)[/latex] è [latex]\Theta (n)[/latex].

Nelle equazioni di ricorrenza che sfruttano questa tecnica poi, appare anche una funzione [latex]f(n)[/latex] che è incaricata di suddividere e ricombinare le soluzioni.

Risolvere un’equazione di ricorrenza usando il teorema dell’esperto

Data dunque una equazione di ricorrenza come quella di poco fa’, il teorema master è composto da 3 casi:

  1. [latex]T(n) = \phi (n^{log _b a}) \text{ se } f(n) = O(n^ {\log _b a – \epsilon }) \text{ per qualche } \epsilon > 0[/latex]
  2. [latex]T(n) = \phi (n^{log _b a}log _2 n) \text{ se } f(n)= \phi (n^{\log _b a} ) )[/latex]
  3. [latex]T(n) = \phi (f(n)) \text{ se } af(n/b) \leq cf(n) \text{ per qualche } c<1[/latex]

Per risolvere quindi una equazione di ricorrenza come quella di cui sopra, dovremo cercare di ricondurla ad uno di questi tre case.

Un esempio di utilizzo, lo trovi dentro all’articolo sul MergeSort(che verrà pubblicato a breve).

Ricorda: il teorema master è potente e facile da utilizzare, ma a volte potrebbe non essere sufficiente per riuscire a risolvere un equazione di ricorrenza che sia nella forma vista prima.