Master theorem
Clicca QUI per vedere il messaggio nel forum |
| pintu |
| Qual'è l'enunciato del master theorem?? |
| panzone |
Un' equazione generatrice del tipo:
T(n) = a T(n/b) + xn^c
può essere asintotica a:
T(n) = Teta(n^c) se a< b^c
T(n) = Teta( n^ c log n ) se a = b^c
T(n) = Teta( n^ log base b di a ) se a > b^c
Ovvero, messa giù in termini umani: visto che l' equazione di ricorrenza sopra rappresenta un generico calcolo del tempo di una procedura dividi et impera, questo valore è asintotico a quale tra la fase di suddivisione del problema ( aT(n/b) ) e la fase di ricostruzione del risultato ( xn^c ) è dominante. L' esempio perfetto è mergesort. Difatti:
T(n) = 2T(n/2) + n-1
n-1 è asintotico ad n, ergo posso vederla come
T(n) = 2T(n/2) + n
Intuitivamente, dividere il problema in due parti uguali ( T(n/2) ) e calcolare le singole parti ha un costo uguale ad n, ovvero la fase di ricostruzione. Ergo la fase di suddivisione e di riunione del problema son di stessa dimensione ergo è il caso centrale, ovvero Teta(n log n ). Ma se vogliamo fare le cose bene:
a= 2 b=2 c=1
ergo 2=2^1 ergo vale Teta(n^1 log n).
La dimostrazione passa per il calcolo della funzione generatrice. |
| Seoman |
Scusate l'intrusione, ma giusto in merito al Master Theorem: io al tempo me lo ero studiato per i fatti miei, 'a parte' dalle dispense (anche perché non credo sia nemmeno presente ..)
Adesso che ho ripreso in mano il malloppo da ripassare\ristudiare per l'orale non riesco a trovare una corrispondenza di argomenti, e la mia domanda è:
i capitoli sulle equazioni di ricorrenza e sulle funzioni generatrici sono da fare giusto per capire l'analisi della ricorsione e le dimostrazioni dei tre casi del Theorem oppure vengono chiesti 'specificatamente' all'esame ?
GRazie |
| pintu |
| Non vengono richiesti direttamente all'esame però bisogna sapere risolvere le equazioni di ricorrenza dei tempi di calcolo degli algoritmi principali. A me all'orale aveva messo davanti l'equazione di ricorrenza di Mergesort e mi aveva chiesto di risolverla..Cerca di studiare i casi specifici.. Per quanto riguarda il capitolo sulle funzioni generatrici io non lo avevo fatto! |
| Seoman |
| GRazie per la risposta, era più o meno quello che avevo in mente; anche perché le dimostrazioni dei tempi di calcolo degli algoritmi fondamentali sono abbastanza rigide, se viene implementata la ricorsione c'è anche l'equazione di ricorrenza associata. |
|
|
|
