Suocen sam sa sledecim problemom. Naime, data je sekvenca odgovarajucih koeficijenata, ali tako da vrednosti
koeficijenate oznacavaju rank, ali relativne vrednosti mogu biti kasnije dovoditi do pogresnih zakljucaka.
Npr.
Sekvenca A: 3, 78, 2, 9848, 456, 2, 455667
Ocigledno, treci i sesti element imaju najmanji rank, sledi prvi element, itd. Medjutim, vrednosti koeficijenata u
sekvenci imaju prilicno veliku diskrepancu (vrednost poslednjeg elementa je daleko veca od vrednosti treceg, a, u sustini
9999 bi, npr, bio dovoljno informativan da najvecu vrednost u sekvenci).
Da bih smanjio razlike (diskrepance), uzimam u obzir monotonu transformaciju, npr log ili koren svakog broja, i tako
snizavam vece vrednosti, a konacan rezultat i dalje odrzava rank.
Dalje, oduzimanje konstante od elemenata sekvence odrzava rank, ali, buduci da je najmanja vrednost elementa u
sekvenci prilicno mala, ovaj postupak ne bi puno promenio u diskrepanci.
Naravno, da bih dobio vrednost sa diskrepancom 1, mogao bih sortirati sekvencu A'=A, i onda, redom trazio elemente iz
A u A'. Medjutim, taj proces oduzima prilicno vremena za velike sekvence: ako je n elemenata, sortiranje je n*log(n), a
trazenje svakog elementa je log(n) (binarnim trazenjem).
Zanima me da li postoje efikasniji nacini da se smanji diskrepanca izmedju uzastopnih elemenata sekvence, pored gore
navedenih.