In questo tutorial imparerai cos'è il teorema principale e come viene utilizzato per risolvere le relazioni di ricorrenza.
Il metodo master è una formula per risolvere le relazioni di ricorrenza del modulo:
T (n) = aT (n / b) + f (n), dove, n = dimensione dell'input a = numero di sottoproblemi nella ricorsione n / b = dimensione di ogni sottoproblema. Si presume che tutti i sottoproblemi abbiano la stessa dimensione. f (n) = costo del lavoro svolto al di fuori della chiamata ricorsiva, che include il costo della divisione del problema e il costo dell'unione delle soluzioni Qui a ≧ 1 eb> 1 sono costanti e f (n) è un asintoticamente positivo funzione.
Una funzione asintoticamente positiva significa che per un valore sufficientemente grande di n, abbiamo f(n)> 0.
Il teorema master viene utilizzato per calcolare la complessità temporale delle relazioni di ricorrenza (algoritmi divide et impera) in modo semplice e veloce.
Teorema del maestro
Se a ≧ 1e b> 1sono costanti ed f(n)è una funzione asintoticamente positiva, la complessità temporale di una relazione ricorsiva è data da
T (n) = aT (n / b) + f (n) dove, T (n) ha i seguenti limiti asintotici: 1. Se f (n) = O (n log b a-ϵ ), allora T (n ) = Θ (n log b a ). 2. Se f (n) = Θ (n log b a ), allora T (n) = Θ (n log b a * log n). 3. Se f (n) = Ω (n log b a + ϵ ), allora T (n) = Θ (f (n)). ϵ> 0 è una costante.
Ciascuna delle condizioni di cui sopra può essere interpretata come:
- Se il costo della risoluzione dei sottoproblemi ad ogni livello aumenta di un certo fattore, il valore di
f(n)diventerà polinomialmente inferiore a . Pertanto, la complessità temporale è oppressa dal costo dell'ultimo livello, ad es.nlogb anlogb a - Se il costo per risolvere il problema secondario a ciascun livello è quasi uguale, il valore di
f(n)sarà . Pertanto, la complessità temporale sarà moltiplicata per il numero totale di livelli, ad es.nlogb af(n)nlogb a * log n - Se il costo della risoluzione dei sottoproblemi a ciascun livello diminuisce di un certo fattore, il valore di
f(n)diventerà polinomialmente maggiore di . Pertanto, la complessità temporale è oppressa dal costo di .nlogb af(n)
Esempio risolto di teorema principale
T (n) = 3T (n / 2) + n2 Qui, a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 ie. f (n) <n log b a + ϵ , dove, ϵ è una costante. Il caso 3 implica qui. Quindi, T (n) = f (n) = Θ (n 2 )
Limitazioni del Teorema del Maestro
Il teorema principale non può essere utilizzato se:
- T (n) non è monotono. per esempio.
T(n) = sin n f(n)non è un polinomio. per esempio.f(n) = 2n- a non è una costante. per esempio.
a = 2n a < 1
