Algorytm magicznych piątek


(Marthy) #1

Czy ktoś zna jakieś namiary na opis tego algorytmu?


(system) #2

A o co chodzi w tym algorytmie, bo może będę mógł pomóc.


(Marthy) #3

No właśnie nie wiem o co chodzi,a muszę sie dowiedzieć :slight_smile: (Możliwe, że ma coś wspólnego z Quicksortem , tudzież z algorytmem Hoare'a...)


(Monczkin) #4

http://www.algorytm.cad.pl/

poszukaj tu

i tu

Złączono Posta : 22 Sierpień 2005, 22:53:04

raczej napewno

http://www.math.uni.opole.pl/isz/ppko.html


(Marthy) #5

Niestety... nie ma :frowning: Może ten algorytm ma jakąś inną nazwę, sama nie wiem...


(Monczkin) #6

http://www.algorytm.cad.pl/


(Marthy) #7

Tak, to znalazlam, ale w dalszym ciągu nic nigdzie nie widzę na temat "magicznych piątek".


(_gosc_) #8

Kluczem do wydajnosci quicksorta i wyszukiwania n-tego elementu jest wybór elementu wzgledem ktorego dzielimy zbior - gdyby w quicksorcie za kazdym razem dzielic n na n-1 i 1 dzialalby w n^2

Najlepiej wybrac element dzielacy dokladnie na pol, czyli mediane - i do tego mniej wiecej sluza magiczne piatki - algorytm wyznacza *pseudomediane*, ktora jest dobra w tym sensie, ze zapewnia zawsze liniowy czasz dzialania algorytmu.

Dzialanie - podziel input na grupki 5 elementowe i z kazdej takiej grupki wylicz mediane (prawdziwa), nastepnie z otrzymane mediany potraktuj w taki sam sposob (i tak w kolko), az otrzymasz tylko 1 mediane.

przyklad nie dla 5, ale 3

213 156 78 65 34 48000000 78 68

(213 156 78 ) ( 65 34 48000000 ) (78 68 )

156 65 73

73

i podzial:

34 65 68 78 78 156 213 48000000

Jak dobrze zaimplementujesz powinno zuzyc rzedu log n dodatkowej pamieci : D

Opoznienie calkiem spore, ale jestescie pierwszym trafieniem w googlu i nie macie wyjasnienia ; )

Drugie trafienie to notatki na http://www.ii.uni.wroc.pl/~lorys/AiSD05/AiSD05.htm

btw: nie moglibyscie dac mozliwosci pisania postow z goscia?

btw2: pozdr dla wszystkich innych, ktorzy tez nie byli na wykladzie :mrgreen: (i zrobili :o na widok "magicznych" piatek)