bartekltg <b...@g...com> napisał(a):

> W dniu 2012-01-30 02:47, M.M. pisze:
> > 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?
>
>
> http://www.youtube.com/watch?v=gENVB6tjq_M
>
>
>
> Odchylenie standardowe to pierwiastek wariancji.
>
> Var(X) = E[ (X-E(X))^2 ] =...= E(X^2) - E(X)^2
>
> Korzystamy z drugiej wersji.
>
> Pisząc po ludzku sum_{i=1}^k (x_i^2/k)/k - ( sum_{i=1}^k x_i )^2/k

Dzieki serdeczne, zapomnialem o drugim wzorze
Pozdrawiam!



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/