Dnia 30-01-2012 o 02:47:21 M.M. <m...@n...gazeta.pl> napisał(a):

> Czesc
>
> Jest liniowa tablica malych liczb staloprzecinkowych
> int tablica[1..N];
> N jest dosc duze, rzedu 100tys do 10mln.
>
> Jest tablica indeksow
> int index[1..M]
>
> Kazdy index[i] dzieli tablice na pare tablic:
> tablica_a[1..index[i]]
> tablice_b[index[i]+1..N]
>
> Czyli tablica_a ma index[i] pierwszych elementow z tablicy
> a tablica_b ma elementy pozostale.
>
> Zadanie jest takie, aby szybko oszacowac odchylenie standardowe dla
> kazdej
> pary tablic ( dla kazdej tablicy w kazdej parze, razem 2*M odchylen ).
> M niestety moze przyjmowac duze wartosci, a wiec par moze byc duzo,
> np. M ~= N / log(N).
>
> Mozna to policzyc jakims algorytmem online, albo np. algorytmem ktory
> przebiega cala tablice nie wiecej niz 10 razy?

moze cos takiego zadziala:

//input:
int tablica[1..N];
int indeksy[1..M];
//output:
int sigma_lower[1..M];
int sigma_upper[1..M];
//temp:
int tmp_sx[1..N];
int tmp_sxx[1..N];

int sx=0;
int sxx=0;
//prepare
for(int i=1;i<=N;i++){
sx=tmp_sx[i]=sx+tablica[i];
sxx=tmp_sxx[i]=sxx+tablica[i]*tablica[i];
}
//use
for(int j=1;j<=M;j++){
sigma_lower[j]=sqrt(tmp_sxx[indeksy[j]]/indeksy[j]-(
tmp_sx[indeksy[j]]/indeksy[j])*(tmp_sx[indeksy[j]]/i
ndeksy[j]);
sigma_upper[j]=sqrt((sxx-tmp_sxx[indeksy[j]])/(N-ind
eksy[j])-((sx-tmp_sx[indeksy[j]])/(N-indeksy[j]))*((
sx-tmp_sx[indeksy[j]])/(N-indeksy[j])));
}

czas bedzie rzedu N+M, dodatkowa pamiec rzedu N
w sumie to od razu moglbys policzyc se odchylenia dla wszystkich podzialow
tablicy


--
Jordan Szubert