[HELP] Funzione di Ackermann
Clicca QUI per vedere il messaggio nel forum |
| kingoff |
| Qualcuno ha idea di come si utilizzi la funzione di Ackermann nella valutazione della complessità degli algoritmi per insiemi disgiunti? |
| Ariok |
| sto scaricando la lezione ora... se faccio in tempo do un 'occhiata.... |
| kingoff |
tra l'altro 22 visite e (per ora) 0 risposte vuol dire che molta gente è impreparata....oppure ha le mie stesse identiche lacune!!
Mi chiedo se sia la prima o la seconda.....
...o magari solo pigrizia...... |
| kingoff |
| 37 visite!!!!!nesssuno lo sa!!! |
| Simeon |
Originally posted by kingoff
Qualcuno ha idea di come si utilizzi la funzione di Ackermann nella valutazione della complessità degli algoritmi per insiemi disgiunti?
Io so solo che applicando le euristiche della compressione del cammino e dell'unione per rango, le operazioni impiegano O(m alfa(n)), dove m e' il numero di MAKE-SET, UNION e FIND-SET, e n e' il numero di MAKE-SET.
alfa(n) e' l'inverso della funzione di Ackermann (che non saprei descrivere perche nella nuova edizione del libro e' strana).
Approfitto pure qua: mi sapete dire se Torelli chiede gli algoritmi sui grafi ? |
| kingoff |
mmm non so...ma devo dire che due tre argomenti li ho tralasciati per approfondirne altri...spero che non mi chiedo tutti e solo quelli che non so!!!
Comunque ho trovato quello che cercavo sulla funzione di ackermann.... |
| Simeon |
Originally posted by kingoff
Comunque ho trovato quello che cercavo sulla funzione di ackermann....
Se è una roba utile a tutti linka pls :asd: |
| kingoff |
allora la funzione di ackermann è una funzione che cresce con una rapidità sorprendente.Prende due parametri, m e n e ha questa forma A(m,n).
Già con A(4,1) manda il pc in stack overflow(!!!!!!!!!!!!!!!!!)
A(m,n)=
n+1 Se m=0
A(m-1,1) se n=0
A(m-1,A(m,n-1)) altrimenti
La risposta alla mia domanda (come si utilizza la funzione di Ackermann nella valutazione della complessità degli algoritmi per insiemi disgiunti?)ha a che fare con questo:
tramite il metodo dell'aggregazione,si può fornire il limite superiore stretto della funzione inversa della funzione di ackermann |
|
|
|
