[Algoritmi] Teorema Master: A che serve e come usarlo

Algorithm Design

[Algoritmi] Teorema Master: A che serve e come usarlo

0

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

Il Teorema Master (Master Theorem) viene utilizzato nello studio di algoritmi per valutare il tempo di esecuzione di algoritmi ricorsivi che sfruttano il concetto di dividi et impera.

Dividi 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 n/b, la risoluzione ricorsiva di questi problemi più semplici e una ricombinazione di tutte le chiamate effettuate.

Nelle equazioni di ricorrenza che sfruttano questa tecnica poi, appare anche una funzione f(n) che è incaricata di suddividere e ricombinare le soluzioni.
T(n) =\begin{cases}1 & \text{per } n = 1\\ aT(n/b) + f(n) & \text{per } n > 1\end{cases}

algorithm-design

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

Presa dunque una equazione di ricorrenza come quella di poco fa, il teorema master ci dà 3 casi:

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

In questo modo, possiamo risolvere velocemente equazioni di ricorrenza della forma vista poco fa, andando semplicemente a verificare di volta in volta in quale dei tre casi ci troviamo.

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

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.

About the Author

Federico PonziStudente, Webmaster ed appassionato di tutto ciò che è informatico con una spruzzata di scienza.View all posts by Federico Ponzi

Leave a Reply