[O.....i]

Taki mam problem mirki:

Dany jest wektor liczb typu double i chciałbym obliczyć ich medianę. Przy posortowanym wektorze nie ma oczywiście żadnego problemu, ale czy da się to jakoś inteligentnie zrobić na wektorze nieposortowanym bez naruszania jego struktury? Na razie jedyne na co wpadłem to skopiować ten cały złom, posortować i sobie sprawdzić, ale to rozwiązanie wydaje mi się strasznie nieekonomiczne.

#kucowanie #programowanie #programujzwykopem

[acetone]

@Onoki: Zaimplementuj tak jak mówisz, a jak ta funkcja zacznie być wąskim gardłem to wtedy wrócisz do optymalizacji.

[O.....i]

@acetone: W sumie masz rację. :/

[Ajakamr]

Algorytm magicznych piątek.

[sylwke3100]

@Onoki:: http://en.cppreference.com/w/cpp/algorithm/sort

Edit o ile to C++

[O.....i]

@sylwke3100: To jest C++ i oczywiście tak właśnie zrobiłem, przeczytaj mój wpis dokładnie. Chciałem tego uniknąć bo quicksort ma jednak tą złożoność O(n*log(n)), co dla stu milionów wylosowanych próbek zaczyna być bardzo bolesne, więc zastanawiałem się czy jest szybszy sposób.

[O.....i]

@Ajakamr: No i o taką odpowiedź właśnie mi chodziło! Liniowa złożoność obliczeniowa, dziękuję, problem rozwiązany. Wystarczy zaimplementować.

Ale na przyszłość wołaj za pomocą małpki i nicka, bo gdyby niżej nie zawołał mnie sylwke to w ogóle nie zobaczyłbym Twojej odpowiedzi. :)

[F.....d]

@Onoki:

1. (someone is wrong on the internet) quicksort ma pesymistyczną złożoność O(n^2), w std::sort to algorytm introsort o pesymistycznej złożoności O(nlogn).

2. Algorytm magicznych piątek jest "ciężki", mimo, że liniowy, to ma dużą stałą i w pesymistycznym przypadku może działać dość długo. Nie wiem, czy dla n ~ 10^8 opłaca się go w ogóle kodzić(log(10^8) wynosi ~27 tj. niedużo).

Jeśli jednak zdecydujesz się go zakodzić, to powiedz, kiedy skończysz :P