View Full Version : [Java] ricerca e ordinamento
wizard1993
29-02-2008, 18:33
salve a tutti, nel mio studio dei linguaggi di programmazzione mi sono ritrovato ad affrontare i sistemi di ricerca e ordinamento.
ora dopo varie analisi mi sono posto alcuni quesiti che da solo non riesco a risolvere (ed essendo autodidatta) e che non so a chi chiedere
1)mettiamo un array utilizzato una sola volta nell'esecuzione di un programma, nel quale va ricercato un valore, qui io ho davanti due alternative: ricerca lineare o ordinamento+ricerca binaria.
se sceglo la prima so che nel caso peggiore avrò una complessità di O(n), se scelgo la seconda avrò per la ricerca una complessità pari a O(log n) più una complessità derivata dall'ordinamento che nel caso dei più efficenti sistemi è di O(n log n).
facendo ora due conti viene fuori che nel primo caso la complessità nel caso peggiore è O(n), nel secondo O(log n+n log n), difatto mettendo un array di 20 elementi nel primo caso avrei 20 confronti, nel secondo 2^4+ 20*2^4=336.
da qui si evince che il primo costa meno del secondo in termini di prestazioni, escludendo gli alberi binari ma operando solo su degli array, esistono altre scappatoie o effettivamente conviene la ricerca lineare?
2) dovendo ordinare una array mi conviene sfruttare un algoritmo di ordinamento, o mi conviene sfruttare gli alberi binari?
wingman87
29-02-2008, 18:39
Scusa ma log(20) non fa 2^4 ;)
Ad ogni modo devi considerare anche il fatto che in genere nel campo pratico le ricerche non si fanno su una quantità di elementi così piccola
PS: mi sono dimenticato di aggiungere che, sempre nel campo pratico, gli elementi non vengono ordinati nel momento in cui devi fare una ricerca ma in genere viene fatto un inserimento ordinato
wizard1993
29-02-2008, 18:44
Scusa ma log(20) non fa 2^4 ;)
Ad ogni modo devi considerare anche il fatto che in genere nel campo pratico le ricerche non si fanno su una quantità di elementi così piccola
PS: mi sono dimenticato di aggiungere che, sempre nel campo pratico, gli elementi non vengono ordinati nel momento in cui devi fare una ricerca ma in genere viene fatto un inserimento ordinato
per il primo punto considero il logaritomo di base due arrotondato per difetto fatto a mente (non trovo una calcolatrice che lo abbia)
per il secondo punto lo so, ma visto che solo per 20 elementi la dimensione aumenta, mi immagino cosa succede con un array di un miliardo, comunque il primo è più una sottigliezza teorica che un qualcosa che mi serve, quel che mi interessa è il secondo punto
wingman87
29-02-2008, 18:49
per il primo punto considero il logaritomo di base due arrotondato per difetto fatto a mente (non trovo una calcolatrice che lo abbia)
per il secondo punto lo so, ma visto che solo per 20 elementi la dimensione aumenta, mi immagino cosa succede con un array di un miliardo, comunque il primo è più una sottigliezza teorica che un qualcosa che mi serve, quel che mi interessa è il secondo punto
Allora log(16)=4 e log(32)=5
Per il secondo punto vedi il PS del mio primo post
EDIT: Aggiungo anche che se non devi fare una sola ricerca ma diciamo n ricerche, è meglio fare l'ordinamento una volta e poi tutte le ricerche con il metodo binario.
salve a tutti, nel mio studio dei linguaggi di programmazzione mi sono ritrovato ad affrontare i sistemi di ricerca e ordinamento.
ora dopo varie analisi mi sono posto alcuni quesiti che da solo non riesco a risolvere (ed essendo autodidatta) e che non so a chi chiedere
1)mettiamo un array utilizzato una sola volta nell'esecuzione di un programma, nel quale va ricercato un valore, qui io ho davanti due alternative: ricerca lineare o ordinamento+ricerca binaria.
se sceglo la prima so che nel caso peggiore avrò una complessità di O(n), se scelgo la seconda avrò per la ricerca una complessità pari a O(log n) più una complessità derivata dall'ordinamento che nel caso dei più efficenti sistemi è di O(n log n).
facendo ora due conti viene fuori che nel primo caso la complessità nel caso peggiore è O(n), nel secondo O(log n+n log n), difatto mettendo un array di 20 elementi nel primo caso avrei 20 confronti, nel secondo 2^4+ 20*2^4=336.
da qui si evince che il primo costa meno del secondo in termini di prestazioni, escludendo gli alberi binari ma operando solo su degli array, esistono altre scappatoie o effettivamente conviene la ricerca lineare?
Certo, se devi cercare qualcosa una volta sola, in un insieme disordinato, allora ti conviene la ricerca lineare.
Resta che se devi cercare l'esistenza di un valore in un insieme, la struttura migliore non e' la lista ordinata. La lista ordinata serve quando devi cercare range di valori (Es: Tutti i valori compresi tra X e Y), oppure quando devi cercare elementi per posizione in una lista ordinata secondo un criterio (ES: Voglio sapere qual e' il quinto elemento se avessi ordinato gli elementi con questo criterio)
Se invece devi cercare semplicemente l'esistenza di un valore in un insieme, la struttura migliore e' la hastable, che si costruisce in O(1) per ogni elemento (quindi O(n) per il tuo caso) e si interroga in poco piu' di O(1) ogni volta che si cerca qualcosa.
Quindi perche' non costruire la hastable anche nel tuo caso limite, ovvero quando si cerca una volta sola, dato che costa O(n)? Perche' la hastable occupa anche memoria, solitamente si approssima per eccesso in 2n, dove n e' l'occupazione della memoria della lista non ordinata di partenza (Sia che sia un array semplice, sia che sia una lista in senso stretto, ovvero in cui ogni elemento ha il proprio valore, e poi il riferimento (puntatore) al prossimo elemento della lista)
Quindi nel tuo caso la complessita' sarebbe O(n) comunque, e, non servendo piu' la hastable, "consumi meno" a scorrere tutta la lista disordinata e cercare il tuo elemento.
Ora, parentesi. E' la terza volta in 3 settimane che mi ritrovo a rinfrescare l'esistenza delle hashtable e dl loro utilizzo. Ma per caso non vengono piu' spiegate? Vengono spiegate male e non si capiscono? Booh?
edit: Scusa, ho visto ora che sei autodidatta, e quindi tanto di cappello per la tua volonta'.
2) dovendo ordinare una array mi conviene sfruttare un algoritmo di ordinamento, o mi conviene sfruttare gli alberi binari?
Io userei un algoritmo di ordinamento, ma solo a pelle, proprio perche' voglio ottenere un array ordinato.
Questo perche' se non sbaglio c'era qualcosa (un teorema? Boh?) che affermava che e' possibile rappresentare un albero binario come una lista ordinata, ma anche il viceversa. Secondo questa affermazione sarebbero equivalenti.
wizard1993
29-02-2008, 20:34
...
questo è quello che volevo sapere.
Per l'ultimo caso però forse ho espresso male la mia richiesta: vorrei sapere se per ordinare un array è più conveniente sfruttare, che ne so, un quicksort, o un ordinamento con albero binario e poi ritirarlo fuori tramite una lettura inordine. ecco quello che vorrei, se non mi sbaglio a livello complessità computazionale il sistema ad albero binario è più efficente se non mi sbaglio log2 n in entrata e lo stesso valore in uscita quindi 2 *(log2 n ), mentre per un quicksort serve n*log n, quindi teoricamente è più conveniente un albero binario, solo che un array occupa meno memoria di un intera classe ricorsiva e si accede più velocemente a dei suoi elementi, quindi non so quanto tempo alla fine possa servire. secondo te quale è più conventiente?
Se invece devi cercare semplicemente l'esistenza di un valore in un insieme, la struttura migliore e' la hastable, che si costruisce in O(1) per ogni elemento (quindi O(n) per il tuo caso) e si interroga in poco piu' di O(1) ogni volta che si cerca qualcosa.
in realtà una ricerca tramite hash table non è in O(1), ma nel caso peggiore è in O(d) dove d è numero di elementi che stanno nella tabella. ma in pratica l'efficienza di una hash table dipende dalla frequenza delle collisioni che a sua volta dipende dal rapporto fra numero massimo di elementi e grandezza della tabella e dalle funzioni di hash utilizzate.
nel caso in esame io userei:
- ricerca lineare se il numero di elementi non è molto grande
- lista ordinata (mediante inserimenti ordinati) + ricerca binaria se il numero di elementi è molto grande
questo è quello che volevo sapere.
Per l'ultimo caso però forse ho espresso male la mia richiesta: vorrei sapere se per ordinare un array è più conveniente sfruttare, che ne so, un quicksort, o un ordinamento con albero binario e poi ritirarlo fuori tramite una lettura inordine. ecco quello che vorrei, se non mi sbaglio a livello complessità computazionale il sistema ad albero binario è più efficente se non mi sbaglio log2 n in entrata e lo stesso valore in uscita quindi 2 *(log2 n ), mentre per un quicksort serve n*log n, quindi teoricamente è più conveniente un albero binario, solo che un array occupa meno memoria di un intera classe ricorsiva e si accede più velocemente a dei suoi elementi, quindi non so quanto tempo alla fine possa servire. secondo te quale è più conventiente?
No, hai sbagliato il costo dell'albero binario.
Vediamo se riesco a farti capire in modo intuitivo il costo:
Immagina di essere a meta' dell'algoritmo di costruzione di un albero binario, ovvero che tu abbia gia' inserito N elementi della tua lista disordinata nell'albero, ma che te ne manchino altrettanti.
Devi inserire l'N+1 esimo. Quanto costa inserirlo? Costa Log(n), perche' log(n) saranno i confronti che dovrai fare (al massimo) per cercare la posizione giusta del tuo nuovo elemento.
E quindi, poiche' ogni elemento costa log(N) , ma tu hai N elementi da inserire nell'albero, ne consegue che anche costruire un albero binario a partire da un insieme disordinato costa N Log(N), proprio come il quicksort e altri algoritmi di ordinamento ottimi.
Anche perche' se avessi trovato un modo di ordinare una lista ordinata in meno di O( N LOG(n)), allora avresti trovato un algoritmo di ordinamento migliore del quicksort, mergesort, etc. E chi ce lo farebbe fare di studiare e usare ancora quegli algoritmi li' e non il tuo?
Concluderei quindi che in quanto a costo sono equivalenti. E questo rafforza la mia ipotesi di prima sul teorema che non ricordo piu', e che sicuramente non riusciro' a trovare.
wizard1993
29-02-2008, 20:58
No, hai sbagliato il costo dell'albero binario.
Vediamo se riesco a farti capire in modo intuitivo il costo:
Immagina di essere a meta' dell'algoritmo di costruzione di un albero binario, ovvero che tu abbia gia' inserito N elementi della tua lista disordinata nell'albero, ma che te ne manchino altrettanti.
Devi inserire l'N+1 esimo. Quanto costa inserirlo? Costa Log(n), perche' log(n) saranno i confronti che dovrai fare (al massimo) per cercare la posizione giusta del tuo nuovo elemento.
E quindi, poiche' ogni elemento costa log(N) , ma tu hai N elementi da inserire nell'albero, ne consegue che anche costruire un albero binario a partire da un insieme disordinato costa N Log(N), proprio come il quicksort e altri algoritmi di ordinamento ottimi.
Anche perche' se avessi trovato un modo di ordinare una lista ordinata in meno di O( N LOG(n)), allora avresti trovato un algoritmo di ordinamento migliore del quicksort, mergesort, etc. E chi ce lo farebbe fare di studiare e usare ancora quegli algoritmi li' e non il tuo?
Concluderei quindi che in quanto a costo sono equivalenti. E questo rafforza la mia ipotesi di prima sul teorema che non ricordo piu', e che sicuramente non riusciro' a trovare.
ok, grazie a tutti
in realtà una ricerca tramite hash table non è in O(1), ma nel caso peggiore è in O(d) dove d è numero di elementi che stanno nella tabella. ma in pratica l'efficienza di una hash table dipende dalla frequenza delle collisioni che a sua volta dipende dal rapporto fra numero massimo di elementi e grandezza della tabella e dalle funzioni di hash utilizzate.
nel caso in esame io userei:
- ricerca lineare se il numero di elementi non è molto grande
- lista ordinata (mediante inserimenti ordinati) + ricerca binaria se il numero di elementi è molto grande
Attento Kont, questo non e' un ragionamento corretto. Nelle valutazioni delle complessita' algoritmiche non si usa il caso peggiore. Altrimenti Quicksort sarebbe O(N^2) e non O(N logN). Anche l'insertion sort da te proposto degraderebbe in O(N^2) nel caso peggiore. Addirittura degrada a O(N^2) piu' in fretta del Quicksort. E' per questo che si preferisce il quicksort invece che l'insertion sort quando ci sono grandi quantitativi di dati da ordinare, in condizioni di limiti di memoria.
Direi quindi che nel caso della ricerca di esistenza la hastable continuerebbe ad essere la migliore anche valutando il caso peggiore.
Attento Kont, questo non e' un ragionamento corretto. Nelle valutazioni delle complessita' algoritmiche non si usa il caso peggiore. Altrimenti Quicksort sarebbe O(N^2) e non O(N logN). Anche l'insertion sort da te proposto degraderebbe in O(N^2) nel caso peggiore. Addirittura degrada a O(N^2) piu' in fretta del Quicksort. E' per questo che si preferisce il quicksort invece che l'insertion sort quando ci sono grandi quantitativi di dati da ordinare, in condizioni di limiti di memoria.
Direi quindi che nel caso della ricerca di esistenza la hastable continuerebbe ad essere la migliore anche valutando il caso peggiore.
beh si usa il caso peggiore... non vedo perchè dovresti preferire un algoritmo che nel caso peggiore è in O(N^2) quando esistono algoritmi che nel caso peggiore sono in O(NlogN), come merge sort o heap sort.
comunque io non ho affatto consigliato insertion sort :fagiano: ho detto che nel caso in cui gli elementi sono molti è conveniente mantenere una lista ordinata mentre li si inseriscono. in questo modo è possibile usare una ricerca binaria.
beh si usa il caso peggiore... non vedo perchè dovresti preferire un algoritmo che nel caso peggiore è in O(N^2) quando esistono algoritmi che nel caso peggiore sono in O(NlogN), come merge sort o heap sort.
comunque io non ho affatto consigliato insertion sort :fagiano: ho detto che nel caso in cui gli elementi sono molti è conveniente mantenere una lista ordinata mentre li si inseriscono. in questo modo è possibile usare una ricerca binaria.
Non ho capito il tuo ragionamento, dove sarebbe O(N^2) la hastable.
Comunque, nel caso peggiore, per costruire una hastable ci metto O(N), e per andare a cercare un valore invece che il "medio (non migliore)" O(1), ci metto di nuovo O(N), perche' tutti gli elementi sono collassati nella stessa chiave.
Quindi a costruirla ci metto O(N) e a cercare ci metto O(N).
Nel caso peggiore quindi siamo a O(N)+O(N) = O(N)
Nel caso medio di un algoritmo di ordinamento tra quelli ottimi, scegli quello che vuoi, ci metterai N LOG(N) ad ordinare, e LOG(N) a cercare.
NLOG(N) + LOG(N) = NLOG(N)
Mi sai dire dove ci guadagni a costruire la lista ordinata per poi cercare dentro?
Invece sul ragionamento "mantenere la lista ordinata mentre li si inseriscono" si puo' applicare sia alla hastable che al caso della lista ordinata.
Per inserire un elemento in una hastable ci metto O(1), per inserirlo in una lista gia' ordinata ci metto O(LOG(N)). Di nuovo, non vedo nessun vantaggio.
Non ho capito il tuo ragionamento, dove sarebbe O(N^2) la hastable.
non ho mai affermato ciò :fagiano:
probabilmente non ci siamo capiti :p
ps. ah per il O(N^2) mi riferivo a quicksort.
quicksort in realtà è molto utilizzato perchè ha una complessità spaziale minore di molti altri algoritmi, non per la sua efficienza temporale (anche se un NlogN nel caso medio è di tutto rispetto)
Comunque, nel caso peggiore, per costruire una hastable ci metto O(N), e per andare a cercare un valore invece che il "medio (non migliore)" O(1), ci metto di nuovo O(N), perche' tutti gli elementi sono collassati nella stessa chiave.
Quindi a costruirla ci metto O(N) e a cercare ci metto O(N).
Nel caso peggiore quindi siamo a O(N)+O(N) = O(N)
Nel caso medio di un algoritmo di ordinamento tra quelli ottimi, scegli quello che vuoi, ci metterai N LOG(N) ad ordinare, e LOG(N) a cercare.
NLOG(N) + LOG(N) = NLOG(N)
Mi sai dire dove ci guadagni a costruire la lista ordinata per poi cercare dentro?
infatti io non ho consigliato da nessuna parte di usare un algoritmo di ordinamento
Invece sul ragionamento "mantenere la lista ordinata mentre li si inseriscono" si puo' applicare sia alla hastable che al caso della lista ordinata.
Per inserire un elemento in una hastable ci metto O(1), per inserirlo in una lista gia' ordinata ci metto O(LOG(N)). Di nuovo, non vedo nessun vantaggio.
il concetto di ordine degli elementi nell'hash table si perde, in ogni caso non è corretto dire che l'inserimento è in O(1). è in O(1) nel caso migliore, ma a questo punto anche nella lista ordinata l'inserimento è in O(1) nel caso migliore (cioè inserisco gli elementi dal più grande al più piccolo).
se valutiamo il caso peggiore allora l'inserimento nella hash table è in O(n) dove n indica il numero di elementi presenti nella hash table (cioè caso in cui l'elemento da inserire collide con tutti gli elementi già presenti).
il concetto di ordine degli elementi nell'hash table si perde, in ogni caso non è corretto dire che l'inserimento è in O(1). è in O(1) nel caso migliore, ma a questo punto anche nella lista ordinata l'inserimento è in O(1) nel caso migliore (cioè inserisco gli elementi dal più grande al più piccolo).
se valutiamo il caso peggiore allora l'inserimento nella hash table è in O(n) dove n indica il numero di elementi presenti nella hash table (cioè caso in cui l'elemento da inserire collide con tutti gli elementi già presenti).
Ecco l'errore. il caso peggiore di inserimento in una hashtable e' sempre O(1).
Anche qualora tu avessi la collisione, e' suffiente appendere l'elemento alla lista degli elementi di quella chiave, tipicamente in coda o in testa. E' sempre O(1), anche nel caso collassato, non hai bisogno di scorrere tutti gli elementi per farlo.
Ecco l'errore. il caso peggiore di inserimento in una hashtable e' sempre O(1).
Anche qualora tu avessi la collisione, e' suffiente appendere l'elemento alla lista degli elementi di quella chiave, tipicamente in coda o in testa. E' sempre O(1), anche nel caso collassato, non hai bisogno di scorrere tutti gli elementi per farlo.
beh nel caso in cui usi il chaining per risolvere le collisioni allora sì, gli inserimenti sono in O(1), io pensavo più ad altre soluzioni. cercare un elemento invece nel caso peggiore (tutti gli elementi collidono) è in O(n), quindi effettivamente potrebbe essere una scelta da prendere in considerazione. ma visto il contesto io non userei una hash table.. se ho pochi elementi la ricerca lineare è in O(n) sempre nel caso peggiore, mentre se ho molti elementi è molto meglio far sì che l'array sia ordinato proprio mentre lo si costruisce per poi poter fare ricerche in log(n) nel caso peggiore. su numeri grossi si vede la differenza.
ps. ciò non toglie che le hash table siano estremamente utili in molti contesti
beh nel caso in cui usi il chaining per risolvere le collisioni allora sì, gli inserimenti sono in O(1), io pensavo più ad altre soluzioni. cercare un elemento invece nel caso peggiore (tutti gli elementi collidono) è in O(n), quindi effettivamente potrebbe essere una scelta da prendere in considerazione. ma visto il contesto io non userei una hash table.. se ho pochi elementi la ricerca lineare è in O(n) sempre nel caso peggiore, mentre se ho molti elementi è molto meglio far sì che l'array sia ordinato proprio mentre lo si costruisce per poi poter fare ricerche in log(n) nel caso peggiore. su numeri grossi si vede la differenza.
ps. ciò non toglie che le hash table siano estremamente utili in molti contesti
Allora, diciamo cosi'.
Se ti senti particolarmente sfortunato usa la lista ordinata, perche' inserisci in O(lOG(N)) e cerchi in O(LOG(N))
Se invece ti senti una persona nella media, allora usa la hashtable, inserisci in O(1) e cerchi in poco piu' di O(1).
Per questo problema, nei grandi numeri io preferisco la hastable, perche' nei grandi numeri e' probabile essere nella media.
Tu che algoritmo useresti per la cache nei microprocessori?
Preferiresti che ogni volta che il microprocessore cerca un indirizzo, allora lo va a cercare in O(Ln(N)) su tutta la cache e ogni volta che deve inserirne uno ci mette O(LN(N)) oppure preferiresti usare una hastable come effettivamente fanno?
Allora, diciamo cosi'.
Se ti senti particolarmente sfortunato usa la lista ordinata, perche' inserisci in O(lOG(N)) e cerchi in O(LOG(N))
Se invece ti senti una persona nella media, allora usa la hashtable, inserisci in O(1) e cerchi in poco piu' di O(1).
ma anche no :fagiano: stai confrontando il caso pessimo del primo con il caso ottimo del secondo. in una hash table cerchi in O(n).
Per questo problema, nei grandi numeri io preferisco la hastable, perche' nei grandi numeri e' probabile essere nella media.
Tu che algoritmo useresti per la cache nei microprocessori?
Preferiresti che ogni volta che il microprocessore cerca un indirizzo, allora lo va a cercare in O(Ln(N)) su tutta la cache e ogni volta che deve inserirne uno ci mette O(LN(N)) oppure preferiresti usare una hastable come effettivamente fanno?
ma non stiamo parlando della cache di un processore giusto?
ma anche no :fagiano: stai confrontando il caso pessimo del primo con il caso ottimo del secondo. in una hash table cerchi in O(n).
In una hashtable si inserisce sempre in O(1), e nel caso medio si cerca in O(1)
Hash tables support the efficient insertion of new entries (O(1)), and the time spent searching for the required data is often independent of the number of items stored (O(1) on average).
ma non stiamo parlando della cache di un processore giusto?
Si', stiamo parlando dell'algoritmo della cache dei processori
Hash tables are often used to implement associative arrays, sets and caches
http://en.wikipedia.org/wiki/Hashtable
In una hashtable si inserisce sempre in O(1), e nel caso medio si cerca in O(1)
sarebbe interessante sapere come hanno calcolato il caso medio, come minimo ci vorrebbero un paio di calcoli di probabilità.
ma in fondo non è che mi interessi più di tanto la faccenda, il mio consiglio l'ho dato e volevo solo precisare che le hash table non risolvono tutti i mali del mondo.
sarebbe interessante sapere come hanno calcolato il caso medio, come minimo ci vorrebbero un paio di calcoli di probabilità.
Hanno solo riportato quello che e' stato calcolato da altri, non e' verbo di Wikipedia.
volevo solo precisare che le hash table non risolvono tutti i mali del mondo.
Ma questo e' poco ma sicuro.
Le hashtable non servono per rispondere a domande tipo:
Quale e' il piu' alto?
Quale e' il piu' basso?
Quale e' il sesto se li ordinassi con questo criterio?
Quali sono i valori tra 5 e 75, presenti in questo elenco?
Per queste risposte ci vuole il concetto di ordinamento, che una hastable classica non ha.
Una lista ordinata invece e' nella maggior parte dei casi il modo migliore, soprattutto se queste domande non sono spot, ma sono ripetute piu' volte nel tempo.
Ma per rispondere a una domanda come "C'e' il 753 in questo elenco di valori disordinati?", che e' proprio la domanda da cui e' partito questo post, allora la hashtable e' la soluzione ottima, soprattutto se la domanda e' ripetuta in modo simile piu' volte nel tempo.
Hanno solo riportato quello che e' stato calcolato da altri, non e' verbo di Wikipedia.
non ci sono riferimenti per quella affermazione, infatti penso proprio che sia inesatta. come minimo la complessità media deve dipendere dal rapporto fra numero di elementi inseriti e dimensione della tabella. ti potrà sembrare che le collisioni siano un'eventualità remota, ma se conosci il paradosso del compleanno capisci che non lo è. per ridurre la probabilità di collisioni di solito si ingrandisce la tabella quando rimangono pochi spazi vuoti. ovviamente sto tralasciando la scelta della funzione di hash, supponendo che sia la migliore immaginabile, ma sappiamo che questo non accade.
detto questo l'hash table è sicuramente una scelta, volevo solo sfatare le sue proprietà magiche.. o forse non posso esprimere il mio parere? :fagiano:
non ci sono riferimenti per quella affermazione, infatti penso proprio che sia inesatta.
E' pieno di riferimenti per quell'affermazione.
Basta che cerchi su google "Hashtable complexity", e tutti ti diranno O(1) sia in inserimento che in ricerca.
O(1) potrebbe significare O(10), o(50), o (1000000), ma senza una N, ovvero che e' indipendente dal numero di elementi che avevi in ingresso.
E' dipendente dal numero di celle della tua hastable e dalla funzione di hashing, che se scelta bene e se non sei sfortunato nella maggior parte dei casi ti permette di avere l'indipendenza appunto dalla quantita' di elementi da trattare.
detto questo l'hash table è sicuramente una scelta, volevo solo sfatare le sue proprietà magiche.. o forse non posso esprimere il mio parere? :fagiano:
Tutti possono esprimere il proprio parere, non ho mai detto questo. Se mi conoscessi personalmente diresti addirittura proprio il contrario.
Ma non venirmi a dire che per quel problema e' mediamente meglio l'uso di una lista ordinata, perche' matematicamente si dimostra che e' meglio un hastable. Nessuna proprieta' magica.
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.