tabelle hash

[gehur]

forse non è la sezione giusta, ma non sapevo dove postare..

la domanda è la seguente: perchè nelle tabelle hash con liste di collisione bidirezionali il tempo di cancellazione è O(1) mentre con liste si collisione unidirezionali il tempo è O(n)??

[gugoXX]

Originariamente inviato da gehur

forse non è la sezione giusta, ma non sapevo dove postare..

la domanda è la seguente: perchè nelle tabelle hash con liste di collisione bidirezionali il tempo di cancellazione è O(1) mentre con liste si collisione unidirezionali il tempo è O(n)??

Sezione giusta direi.

Deriva dal fatto che nelle liste doppio linkate la cancellazione si fa in O(1), mentre nelle liste a single link la cancellazione si fa in O(N).

(In realta' per le hashtable non e' corretto dire O(1) e O(N), ma occorrerebbe dire O(1) e O(M), dove M e il ratio di collisione, ovvero quanti elementi hanno in media la stessa hash, ovvero quando e' appunto in media lunga la lista di collisione nelle hashtable gestite con liste di collisione)

Per cancellare un elemento da una lista linkata occorre aggiornare i puntatori degli elmenti che vi puntano.
Nella doppio likata, per sapere su quali elementi agire quindi e' sufficiente andare a leggere il nodo stesso, che contiene per definizione il successore e il precedente, che dovranno essere aggiornati come se l'elemento da cancellare non esistesse piu'. Quindi O(1), ovvero un numero fisso e costante di operazioni da fare indipendente dalla lunghezza della lista stessa.
Per quanto riguarda invece la lista single linkata (ad esempio in avanti), non sappiamo qual e' l'elemento precedente che deve essere aggiornato puntando al successivo, semplicemente leggendo il nodo da cancellare.
Occorrera' seguire la lista dall'inizio per trovare l'elemento precedente, per poi poterlo aggiornare. Seguire dall'inizio costa O(N).

[cionci]

Sì, è la sezione giusta.
E' la sola operazione di rimozione che è O(1), c'è sempre il costo relativo alla ricerca dell'elemento da eliminare che è proporzionale alla lunghezza.

Con una lista uniderezionale per rimuovere un elemento bisogna invece fare sempre la ricerca, ma bisogna anche ricercare l'elemento precedente in modo da linkare questo elemento a quello successivo a quello da eliminare.

Questo costo aggiuntivo è però facilmente eliminabile, diciamo che se la ricerca dell'elemento viene fatta con cognizione di causa allora verrà mantenuto anche il puntatore all'elemento precedente così che sarà possibile fare l'eliminazione dell'elemento dalla lista in O(1)

Ad esempio:

struct list
{ 
   int info;
   struct list *next;
} *l;

void elimina(int i, struct list **l)
{
   struct list *current = *l, *prev = *l;
   
   while(current->info != i && current != NULL)
   {
      prev = current;
      current = current -> next;
   }

   if(current == NULL)
      return;
   
   if(current == prev)
      *l = current->next;

   prev->next = current->next;
   free(current);   
}

Qui la lista è unidirezionale eppure l'eliminazione è O(n)

[gugoXX]

Originariamente inviato da cionci

Ad esempio:

Anche l'esempio troppo professionale.

[cionci]

Originariamente inviato da gugoXX

Anche l'esempio troppo professionale.

Giusto un esempio, perché non l'ho nemmeno fatto compilare

[astorcas]

Originariamente inviato da cionci

...
Qui la lista è unidirezionale eppure l'eliminazione è O(n)

sono rinc* io o è O(1)?

[cionci]

Originariamente inviato da astorcas

sono rinc* io o è O(1)?

O(1) scusa
La ricerca è O(n), l'eliminazione O(1).

[gehur]

grande ragazzi!! grazie!