Princip interpoliranog pretrazaivanja????
Potpis
maja
Interpolirano pretrazivanje niza
Zaključano
Zakačeno
Ideja je da se pomoću formule dobije približna lokacija tražene vrednosti. Ako se ne dobije tačna lokacija, onda se postupak primenjuje rekurzivno, u zavisnosti od toga gde se nalazi tražena vrednost. Uslov je da je niz sortiran.
Formula:
pozicija = minPozicija + (tražena vrednost - minimalna vrednost)/(maksimalna vrednost - minimalna vrednost)*(maxPozicija-minPozicija)
tj.
Pk = Pmin + (K-MIN)/(MAX-MIN)*(Pmax-Pmin)
P-označava poziciju, a ostale označavaju vrednost promenljive na toj poziciji
Formula se izvodi iz numeričke metode regula falsi.
Postoji i robusno ili brzo interpolaciono pretraživanje koje popravlja performanse kada podaci nisu uniformno raspoređeni.
Formula:
pozicija = minPozicija + (tražena vrednost - minimalna vrednost)/(maksimalna vrednost - minimalna vrednost)*(maxPozicija-minPozicija)
tj.
Pk = Pmin + (K-MIN)/(MAX-MIN)*(Pmax-Pmin)
P-označava poziciju, a ostale označavaju vrednost promenljive na toj poziciji
Formula se izvodi iz numeričke metode regula falsi.
Postoji i robusno ili brzo interpolaciono pretraživanje koje popravlja performanse kada podaci nisu uniformno raspoređeni.
http://www.dcc.uchile.cl/~rbaeza/handbook/algs/3/322.srch.p.html
http://en.wikipedia.org/wiki/Interpolation_search
http://en.wikipedia.org/wiki/Interpolation_search
Potpis
Sendvic uvek pada na namazanu stranu!