Interpolation search: differenze tra le versioni

Versione delle 22:26, 24 dic 2015

Versione delle 23:52, 6 gen 2016

Riga 14:

Ad 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 conronto.

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 log(log(''n'')) confronti (dove ''n'' è 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 [[O-grande|O]](''n'') 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>

Riga 58:

== Collegamenti esterni ==

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

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

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

{{portale|informatica|matematica}}