[ onako @ 16.03.2011. 13:07 ] @
| 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. |