Witam,
Znacie jakieś lepsze od mojej (quicksort - n*log(n)), wyszukiwania median w danym zbiorze elementów?
http://4programmers.net/Forum/viewtopic.php?id=108435
Magiczne piątki, O(n)
Chetnie odpowiem ale po zakonczeniu OI czyli 20 listopada bo to czesc zadania.
Spoko, mam to zrobić na 22 na informatykę, także nie ma problemu. Myślałem tylko, że wcześniej to wykminie, ale trudno. A OI to się nie kończy 19-tego?
Dzięki za link do magicznych piątek.. W sumie to się zastanawiam, czy zastosowanie sortowania przez zliczanie, a następnie wybór środkowego elementu nie będzie równie wydajny co piątki?
Teflon napisał(a)
W sumie to się zastanawiam, czy zastosowanie sortowania przez zliczanie, a następnie wybór środkowego elementu nie będzie równie wydajny co piątki?
tutaj masz za duże uniwersum wartości, żeby zastosować sortowanie przez zliczanie. musisz zrobić coś co jest przez porównania, np: mediana median.
A ma ktoś implementacje Mediany median w C(++)? W linku widziałem, że jest w pascalu, ale jakoś nie widzi mi się przepisywanie tego do C++.
A przy małym uniwersum wartości sortowanie przez zliczanie będzie porównywalne z Medianą median?
_donkey7 napisał(a)
Teflon napisał(a)
W sumie to się zastanawiam, czy zastosowanie sortowania przez zliczanie, a następnie wybór środkowego elementu nie będzie równie wydajny co piątki?
tutaj masz za duże uniwersum wartości, żeby zastosować sortowanie przez zliczanie. musisz zrobić coś co jest przez porównania, np: mediana median.
To sie ort! sortowania, do inta
nawet na waszej stronie jest artykul Radix sort
Pojedyncza mediane da sie obliczyc w O(n) i ponizej nie zejdziemy. i to jest przypadek sredni bo pesymistyczny to chyba n log n ;)
A wielokrotnie obliczanie mediany mozna zrobic w ...
Preprocesing: O(n log n)
Wyciaganie mediany: O( log n)
Pozdrawiam
dżizas, poczytajcie cormena :-/
algorytm magicznych piątek to:
- podziel ciąg wejściowy na pięcioelementowe ciągi
- posortuj je insertionsortem
- wybierz z nich środkowe elementy (mediany)
- z wybranych elementów utwórz ciąg i jeśli ma więcej niż jeden element to idź do kroku 1.
proste jak budowa cepa. trzeba zaznaczyć, że nie jest to zwykle prawdziwa mediana, ale coś koło tego, co najwyżej o jakąś stałą gorsze (czyli oddalone od mediany w ciągu posortowanym) od prawdziwej mediany. używając algorytmu magicznych piątek w algorytmie select (czyli wybór n- tego pod względem wielkości elemtnu w ciągu) możemy uzyskać liniowy pesymistyczny czas wyboru mediany (lub któregokolwiek pod względem wielkości elementu).
jeżeli chcecie uzyskać ciąg median to po prostu posortujcie najpierw ciąg, a potem zaczynając od środka i wychodząc dwoma indeksami na prawo i lewo wybieramy na przemian elementy (czyli tworzy się nam taka symetryczna dziura w środku).
radix sort wymaga dodatkowej pamięci. podobnie jak counting sort. więc odpadają :-)
OI sie skonczyla.
Jezeli chcesz wyznaczac mediane wiele razy dorzucajac cos do zbioru albo usuwajac. To mozesz wykorzystac STLowego seta. Ustawic iterator na srodkowy element a potem dorzucajac cos albo usuwajac iterator +/-
mozesz spokojnie to samo zrobic na swoim drzewku ;) milo i przyjemnie baw sie dobrze pozdrawiam.
Wystarczyło zapytać na innym forum i dostałem odpowiedź beż żadnych ceregieli. Wystarczy użyć drzewa licznikowego, jakby ktoś kiedyś potrzebował.
Całkiem niezły link z opisem algorytmów tegoż drzewa:
http://infa.lo2.opole.pl:81/lekcje/drzewo_licznikowe/drzewo_licznikowe.doc
no nie wydaje mi się, abyś pytał o coś takiego.
drzewo licznikowe jest bardzo podobne do drzewa turniejowego (w zasadzie to drzewo turniejowe, tyle że po ilościach elementów, a nie wartościach elementów), które miałem w zeszłym semestrze na asd ;) (drzewo turniejowe w podstawowej formie służy do wyznaczania sumy elementów ciągu z pewnego zakresu, tzn. od elementu a[i] do a[j] w czasie logarytmicznym - czyli daje operacje suma_elementów(skąd, dokąd) i zmień_element(który, wartość)).
drzewo licznikowe ma taką wadę, że złożoność pamięciowa zależy od wartości liczby n (czyli złożoność wykładnicza względem długości liczby n) co przy pełnym zakresie inta 32 bit daje dziesiątki gigabajtów pamięci :-/
można też odpalić jakieś zwykłe drzewo binarne (posortowane of coz) i w węzłach trzymać moce poddrzew (tzn. ilości potomków). może być zwykłe, avl, czerwono- czarne lub jakiekolwiek inne. zaleta jest taka, że złożoność pamięciowa zależy nie od mocy uniwersum kluczy a od mocy zbioru samych kluczy wejściowych.
jeżeli wiemy jaka jest moc poddrzew to wiemy też jak znaleźć i- ty element (szukamy bardzo podobnie jak w drzewie licznikowym).