Szybkie obliczanie mediany i dominanty

montepasy · Post autor: **montepasy** » 30 gru 2012, o 19:25

Witam

Chciałem zapytać czy istnieje jakiś szybki sposób obliczania mediany i dominanty, analogiczny do sposobu, który jest znany dla średniej arytmetycznej, mianowicie :

Jeśli mamy już daną jakąś średnią, to kiedy do jakiegoś zbioru dodajemy kolejną próbę i z całości chcemy policzyć średnią, to do wcześniejszej wartości średniej jedynie dodajemy wartość nowej próby i dzielimy przez dwa.

Bardzo by mi ułatwiło życie coś takiego dla dominanty i mediany, jednak nie wiem czy podobne wzory w ogóle istnieją..

Dziękuję z góry za pomoc.

Pozdrawiam

pyzol · Post autor: **pyzol** » 30 gru 2012, o 19:36

No niezbyt. Dla mediany musisz ułożyć je w ciąg niemalejący. Interesuje Cię wynik, który jest po środku.
np. \(\displaystyle{ 1,2,5,7,7,9,10}\)
Ciąg ma \(\displaystyle{ 7}\) wyrazów. Więc czwarty wyraz to będzie mediana.
Jedynie \(\displaystyle{ 7}\) powtarza się 2 razy więc jest to również dominanta.
Najszybszy sposób to skorzystanie z programu.

montepasy · Post autor: **montepasy** » 30 gru 2012, o 20:24

No właśnie o to chodzi, że chciałem to wykorzystać w programie, dokładnie w przetwarzaniu obrazów przy modelowaniu tła. Przy każdym update tła słabym rozwiązaniem jest przeliczanie za każdym razem jakiegoś ciągu dla znalezienia dominanty czy mediany i myślałem, że uda się to jakoś inaczej zrobić - szybciej..ale cóż - dzięki za pomoc

pyzol · Post autor: **pyzol** » 30 gru 2012, o 21:04

Jeśli chodzi o medianę, to skorzystanie z algorytmu szybkiego sortowania.
Możesz więc (skoro już masz średnią), zrobić od razu podział na dwie tabele. Liczby mniejsze od średniej oraz liczby większe (bądź równe) od średniej.
Wątpliwa sprawa by trafiło się by były równe, ale bierzemy tą z większą ilością i tam szukamy, Można się bawić w takie "połówkowanie", tylko że napisanie programu nie takie proste.