| | | OFFLINE | Post: 120 | Sesso: Maschile | |
|
01/10/2011 12:16 | |
Simulazione algoritmi di ordinamento: Sort Animation
Esempi alberi:
Alberi binari di ricerca
Gli alberi
AlberiBinari.java[Modificato da ttnd 06/09/2012 14:21] |
|
|
|
| | | OFFLINE | Post: 4 | Città: CROTONE | Età: 40 | Sesso: Maschile | |
|
17/10/2011 20:27 | |
Esempio complessità - Clicca qui public boolean trovaValoreNullo( AlberoB a )
questo metodo restituisce true, appena trova un elemento
dell'albero che sia pari a zero.
false,altrimenti.
public boolean trovaValoreNullo( AlberoB a )
{
// verifico che a possa esistere, se a non esiste
// non posso dire che esiste un valore nullo in esso.
if( a==null ) return false;
// se ho trovato un nodo, la cui parte informativa
// è un valore nullo, allora restituisco true e termino.
if( a.getValore() == 0 )
return true;
// devo continuare ad ispezionare l'albero perchè
// ancora non ho trovato ciò che desideravo. Questo
// valore potrebbe essere in un sotto-albero di sinistra
// o in un sotto-albero di destra
return trovaValoreNullo( a.getSinistro() ) ||
trovaValoreNullo( a.getDestro() );
}//trovaValoreNullo
determino la complessità
Per definizione,
La COMPLESSITA' TEMPORALE è rappresentata dal numero di
operazioni che effettuo, mentre, la COMPLESSITA' SPAZIALE
da quanti record di memoria sto usando per le mie chiamate
ricorsive.
CASO PEGGIORE..
nel caso peggiore devo sempre essere " pessimista ", nel
senso che scelgo come situazione, quella più sfavorevole
possibile al mio algoritmo.
Nel nostro caso, il mio caso peggiore, potrebbe essere che
l'albero non contenga nessun valore nullo e quindi ispeziono
tutti i nodi inutilmente; visto che non trovo quello che a
me interessa. Un'altro caso sfavorevole potrebbe essere che
il nodo che sto cercando sia alla massima profondità dell'albero.
In parole povere, in entrambi i casi, sto controllando tutti
i nodi dell'albero e quindi faccio almeno N OPERAZIONI di visita.
Quindi, posso dire che la mia complessità nel caso peggiore è Teta(N).
CASO MIGLIORE..
nel caso migliore devo essere più " allegretto " possibile, nel
senso cerco il caso più semplice che il mio algoritmo possa
trattare. Escludi subito, il caso in cui l'albero non esiste o
che PASSI UN SOLO NODO. Sono due errori gravi; tu passi sempre
e comunque un intero albero, anche nel caso migliore.
il mio caso migliore è che il mio valore nullo che cerco è proprio
presente sulla radice. Quindi, i metodi ricorsivi non vengono eseguiti
ma viene eseguito solo
if( a.getValore() == 0 )
return true;
e quindi fai al più una operazione di visita, quindi, Teta( 1 ).
COMPLESSITA' SPAZIALE
CASO PEGGIORE..
In termini di memoria, il mio caso peggiore è che l'albero sia degenere.
Un albero degenere è un albero sbilanciato o tutto a sinistra o tutto
a destra e puoi trattarlo come una normale lista concatenata.
Nel caso peggiore, come detto prima, il valore che cerco non esiste
o sia presente alla massima profondità dell'albero.
Questo mi porterà ad invocare almeno N-volte la coppia dei due metodi
ricorsivi, uno a sinistra e uno a destra.. quindi avrò N-record attivi in memoria.
N-Record attivi perchè appunto è un albero degenere..
Quindi avrò una complessità spaziale pari a Teta(N).
( in parole povere, invoco la coppia dei metodi n volte )
CASO MIGLIORE..
Nel caso migliore, si ragiona davvero poco. Noi sappiamo che la
complessità SPAZIALE non può mai essere maggiore della complessità
TEMPORALE. Essendo che la temporale è venuta Teta(1) allora dico
che la spaziale è Teta(1). Se invece, devo fare due conti posso
dire...
Essendo che il nodo che cerco è presente gia sulla radice ed
essendo che viene invoco solo
if( a.getValore() == 0 )
return true;
senza alcuna chiamata ricorsiva, allora, avrò un solo record attivo
in memoria; invoco il metodo una sola volta. Teta(1).
[Modificato da ttnd 06/09/2012 14:24] |
|
| | | OFFLINE | Post: 120 | Sesso: Maschile | |
|
19/10/2011 21:56 | |
Ottimo collega! Grande spiegazione!!! |
|
|
|