Witam,
Znacie jakieś lepsze od mojej (quicksort - n*log(n)), wyszukiwania median w danym zbiorze elementów?
0
0
http://4programmers.net/Forum/viewtopic.php?id=108435
Magiczne piątki, O(n)
0
Chetnie odpowiem ale po zakonczeniu OI czyli 20 listopada bo to czesc zadania.
0
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?
0
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.
0
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?
0
_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
0
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
0
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ą :-)
0
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.
0
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
0
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).