Newsgroup: it.comp.lang.c++
Titolo: Hash

Ciao,
avrei un dubbio su una questione riguardante le HASH TABLE.
La complessità per la ricerca di un elemento con tale rappresentazione è:
O(Log(n)).
Tale valore si può derivare ragionando sul fatto che nel caso migliore O(1)
l' array degli indici è di dimensione uguale al numero di elementi da
memorizzare  in tabella ,in modo da avere liste con 1 elemento ciascuna, in
tal caso il costo è quello di una assegnazione ,nel caso peggiore invece ho
un array di dimensione 1,  ho praticamente una lista che richiede algoritmi
di ricerca di ordine O(n).
Riassumendo ,nel caso medio ho una complessità che è maggiore di O(1) ma
minore di O(n) quindi unica alternativa è O(Log(n)).
Vorrei sapere se questo ragionamento (ammetto un po' forzato) è valido o
meno.
Ringrazio anticipatamente per l'eventuale risposta.
Leonardo ING. TLC Napoli
lettieri...@hotmail.com

]

 meno.
Se è solo per aiutarti a capire, può anche andare bene, ma non dirlo mai ad
un prof. :-)
Considera anche che tra O(1) e O(n) non esiste proprio solo O(Log(x)), anche
se certo è la funzione più importante.


In genere, la complessità di un algoritmo si valuta sul caso peggiore, non su
quello medio (o su quello ottimo). Negli ultimi due casi, infatti, va precisato
il tipo di analisi effettuata. In altre parole, puoi dire che Quicksort, *nel
caso medio* ha complessità O(nlogn) ma non puoi dire che l'algoritmo *è* di
complessità O(nlogn). Quicksort resta di complessità O(n^2).
AB
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Andrea Baruzzo
Via Circonvallazione, 26
Muzzana del Turgnano (UD) - Italy
e-mail: 
andrea....@ud.nettuno.it
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Ringrazio anticipatamente per l'eventuale risposta.
NOTA:
  Follow-up su      it.scienza.informatica
E` un ragionamento sbagliato.
L'operazione di ricerca (inserimento) in una tabella hash e` O(n) nel 
caso pessimo. Se non ci sono collisioni l'operazione costa 1, ma in
caso di collisione bisogna scorrere la tabella fino a trovare cio` che 
si cerca.
Il caso medio in genere si calcola statisticamente sulla base delle
probabilita` di H (funzione hash)
Supponendo che le chiavi abbiano distribuzione uniforme
sulla tabella (quindi valori di H equiprobabili), facendo delle
simulazioni risulta che in media l'operazione costa sempre O(1) perche` 
al piu` basta scorrere una minima frazione della tabella (pochi accessi)
per ottenere il risultato.
Ovviamente tutto cio` dipende da 2 fattori:
1) Costo della funzione hash
2) Dimensione della tabella.
1) Si suppone che H sia calcolabile in O(1) altrimenti
    una operazione non puo` avere costo O(1) neanche nel caso
    ottimo.
2) La tabella non deve essere troppo precisa, altrimenti il
     rischio di collisioni aumenta, soprattutto se la distribuzione
     di H non e` abbastanza uniforme.
Sulle tabelle hash ci sono presumibilmente molti studi, ma che io
sappia nessuno fornisce indicazioni precise su come dimensionare
una tabella. In generale ci sono indicazioni che nascono da studi
statistici di casi piu` o meno frequenti e comunque tutto dipende
dalla qualita` di H (infatti in genere la supposizione iniziale e`
l'equiprobabilita` di H(x)).
Paolo
-----------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
-----------------------------------------------

se certo è la funzione più importante.
Oltretutto il caso medio solitamente si calcola come media del caso
ottimo e di quello pessimo, tenendo conto delle probabilita` dei
possibili eventi.





Beh allora come diavolo arrivo alla conclusione che la complessitą č Logn?
Non ci puoi arrivare perche' non e' log(n)


 Un ragionamento valido ci sarà...
Nel caso in particolare non saprei, non essendo molto ferrato sulle hash
table (mai usate), ma su altri algoritmi (tipo ricerca su alberi binari
ordinati e bilanciati) la dimostrazione è facilissima.
Ah, un caso ancora più facile: indovinare un numero compreso tra 1 e n
sapendo solo se il numero è maggiore o minore di quello tentato. Richiede
log2(n) tentativi, no? (arrotondando per eccesso al numero intero superiore)
E questo è il caso peggiore, quello medio dovrebbe essere intorno a
log2(n)-1, ma se servisse si può calcolare esplicitamente ed esattamente per
un po' di n.
--
Alessandro Monti

Beh allora come diavolo arrivo alla conclusione che la complessità è Logn?
Infatti non mi pare che la complessita` sia O(Log(n))!
followup su    it.scienza.informatica
