|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-19 10:29:57
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv28133 Modified Files: relazione.dvi relazione.pdf relazione.tex Log Message: Index: relazione.pdf =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.pdf,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 Binary files /tmp/cvstKt8CY and /tmp/cvsRXlnT8 differ Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 Binary files /tmp/cvsKDbpZm and /tmp/cvsq8CIqx differ Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.15 retrieving revision 1.16 diff -C2 -d -r1.15 -r1.16 *** relazione.tex 19 Sep 2004 10:07:27 -0000 1.15 --- relazione.tex 19 Sep 2004 10:29:44 -0000 1.16 *************** *** 420,424 **** L'inserimento di una sequenza di valori sempre crescenti in un albero binario rappresenta il caso peggiore (insieme a quello di inserimento di valori sempre decrescenti) se si sta utilizzando un'implementazione semplice BST ma non influisce in modo significativo nel caso in cui si utilizzi un'implementazione AVL. In questo caso, infatti, un albero BST degenera in una lista nella quale l'inserimento di un nuovo valore viene fatto sempre in coda e che quindi presenta un costo di inserimento pari a $O\left(n\right)$. ! Il grafico avvalora quanto detto. Infatti la curva relativa agli AVL si presenta con un andamento grossomodo costante, ovvero logaritmico mentre quella relativa ai BST cresce in maniera lineare con una pendenza molto elevata facendo in modo che la prima curva sia sempre minore della seconda anche per dimensioni di input non troppo elevate. \begin{center} --- 420,431 ---- L'inserimento di una sequenza di valori sempre crescenti in un albero binario rappresenta il caso peggiore (insieme a quello di inserimento di valori sempre decrescenti) se si sta utilizzando un'implementazione semplice BST ma non influisce in modo significativo nel caso in cui si utilizzi un'implementazione AVL. In questo caso, infatti, un albero BST degenera in una lista nella quale l'inserimento di un nuovo valore viene fatto sempre in coda e che quindi presenta un costo di inserimento pari a $O\left(n\right)$. ! In particolare il primo inserimento sull'albero vuoto ha un costo pari a $c$ ovvero una costante. Il secondo inserimento ha un costo pari a $c + c1 \approx c$ ovvero il costo della vistia del nodo inserito precedentemente pi\`u il costo del nuovo inserimento. Al generico inserimento (l'$i$-esimo) si ha un costo par a circa $ci$. Il costo totale si ottiente sommando tutti i costi parziali fino ad $i = n$. ! \[ ! \sum_{i=1}^n ci = c \frac{n\left(n-1\right)}{2} = O\left(n^2\right) ! \]. ! ! Per quanto riguarda gli AVL ogni inserimento ha costo $O\left(h\right)$ dove $h$ \`e l'altezza dell'albero. Visto che si fanno $n$ inserimenti il costo sar\`a $O\left(nh\right)$. L'altezza dell'albero varia in base alla sua dimensione ma \`e sempre possibile maggiorarla con $\log\left(n\right)$ e quindi si pu\`o affermare che il costo totale per l'implementazione AVL sar\`a al pi\`u $O\left(n\log\left(n\right)\right)$. ! ! Il grafico avvalora quanto detto. Infatti la curva relativa agli AVL si presenta con un andamento grossomodo costante, ovvero logaritmico mentre quella relativa ai BST cresce in maggiore rispetto ad un andamento lineare e con una pendenza molto elevata e crescente facendo in modo che la prima curva sia sempre minore della seconda anche per dimensioni di input non troppo elevate. \begin{center} |
