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


Ponieważ masz inty, nie musisz sie przejmować stratą dokładności
(np licząc odchylenie z dużęj próbki X ~ N(1,10^-12) lepiej użyć
pierwszego wzoru;) uważaj jedynie na zakres, bo prawie na pewno
przekroczysz int32, a dla odpowiednich danych i int64)

Liczysz więc na bieżąco sumę i sumę kwadratów, zapisujesz
je dla każdego k z tablicy index.
Potem za ich pomocą (oraz sumy i sumy kwadratów wszystkich)
obliczasz odchylenie w odpowiednich podtablicach.

Podsumowując masz jeden przejazd po 'tablica' z zapisywaniem
do tablic długości M (suma i suma kwadratów) a następnie
przelecenie tych tablic i wpisanie wyników (uważaj na związek
indeksu i długości przedziału==liczności próbki i pamiętaj
o pierwiastku:) IMHO najpierw odejmowanie, potem zrzut
na double i dzielenie.


pzdr
bartekltg