Interpolation search: differenze tra le versioni

Versione delle 23:37, 11 gen 2017

Versione attuale delle 21:23, 1 ott 2024

(6 versioni intermedie di 6 utenti non mostrate)

Riga 1:

{{Algoritmo

|classclasse = [[Algoritmo di ricerca]]

|immagine =Interpolation sort.gif

|image=

|didascalia =Ricerca del numero 24 grazie all'algoritmo

|caption=

|datastruttura dati = [[Array]] ordinato

|tempo = <math>O(n)</math>

|time=n

|tempo migliore = <math>O(1)</math>

|best-time=1

|average-timetempo medio = <math>log(log(''n''))</math>

|spacespazio =

|ottimale =

|optimal=

}}

L{{'}}'''interpolation search''' è un [[algoritmo di ricerca]] di un dato valore chiave in un [[array]] ordinato tramite gli stessi valori delle chiavi. È il metodo corrispondente alla ricerca di un particolare termine all'interno di un [[dizionario]] o di un nominativo all'interno di un [[elenco telefonico]].

AdA ogni passo della ricerca, l'algoritmo valuta dove può trovarsi l'elemento all'interno del ''search space'' basandosi sui valori delle chiavi agli estremi dell'array e sul valore da cercare. Dopodiché confronta la chiave selezionata con il valore da cercare. Se si tratta del valore richiesto, allora l'algoritmo è terminato. Altrimenti il ''search space'' viene sostituito con la parte restante destra o sinistra dell'array, a seconda del risultato del confronto.

L'interpolation search può essere considerato come una generalizzazione della [[ricerca dicotomica]]; quest'ultima, infatti, segue lo stesso procedimento, ma non si basa sui valori degli estremi, bensì taglia il ''search space'' sempre a metà.

In media, il costo dell'algoritmo è di <math>log(log(''n''))</math> confronti (dove ''<math>n''</math> è la dimensione dell'array), ma è efficace solo se le chiavi sono distribuite in maniera ragionevolmente uniforme, ovvero se la differenza fra due valori contigui è pressoché costante. Nel caso peggiore (ad esempio, se il valore numerico delle chiavi aumenta esponenzialmente), si avranno [[<math>O-grande|O]](''n'')</math> confronti.<ref>Weiss, Mark Allen (2006). ''Data structures and problem solving using Java'', Pearson Addison Wesley</ref><ref>Armenakis, A. C., Garey, L. E., Gupta, R. D., An adaptation of a root finding method to searching ordered disk files, BIT Numerical Mathematics, Volume 25, Number 4 / December, 1985.</ref><ref>Sedgewick, Robert (1990), ''Algorithms in C'', Addison-Wesley</ref>

== Esempio di implementazione ==

Il seguente codice [[C++]] è un esempio di semplice implementazione. AdA ogni passo calcola una possibile posizione del valore, per poi restringere l'intervallo —come nella ricerca binaria—binaria — aumentando il ''lower bound'' o diminuendo l{{'}}''upper bound''.

<sourcesyntaxhighlight lang="cpp" line="1">

template <typename T>

int interpolation_search(T arr[], int size, T key)

Riga 44:

return -1;

}

</syntaxhighlight>

</source>

<!-- Notice that having probed the list at index ''mid'', for reasons of loop control administration, this code sets either ''high'' or ''low'' to be not ''mid'' but an adjacent index, which ___location is then probed during the next iteration. Since an adjacent entry's value will not be much different the interpolation calculation is not much improved by this one step adjustment, at the cost of an additional reference to distant memory such as disc.

Riga 53:

== Voci correlate ==

* [[Ricerca sequenziale]]

* [[Ricerca dicotomica]]

* [[Hash table]]

== Collegamenti esterni ==

* {{cita web|http://www.dcc.uchile.cl/~rbaeza/handbook/algs/3/322.srch.p.html|Interpolation search|lingua=en}}

* {{cita web|http://www.nist.gov/dads/HTML/interpolationSearch.html|National Institute of Standards and Technology|lingua=en}}

* {{cita web|http://www.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdf|Interpolation Search - A Log LogN Search|lingua=en}}

{{portalePortale|informatica|matematica}}

[[Categoria:Algoritmi di ricerca]]