#programowanie #naukaprogramowania #algorytmika
Zadanie wybierz k największych elementów z pośród n. gdzie n>>k
na chama to będzie dane.sort().head(10) ale złożoność nlogn +k bo sortowanie nie da się szybciej
tak pomyślałem że można by zaalokować drzewo na k elementów i mieć zawsze "pod ręką" wartości max/min w drzewie by wiedzieć czy jest sens wykonywać drogie wstawianie. przy jednorazowym przelocie przez zbiór
no i wyszła mi złożoność nlogk. ktoś da mniej?( ͡° ͜ʖ ͡°)
Zadanie wybierz k największych elementów z pośród n. gdzie n>>k
na chama to będzie dane.sort().head(10) ale złożoność nlogn +k bo sortowanie nie da się szybciej
tak pomyślałem że można by zaalokować drzewo na k elementów i mieć zawsze "pod ręką" wartości max/min w drzewie by wiedzieć czy jest sens wykonywać drogie wstawianie. przy jednorazowym przelocie przez zbiór
no i wyszła mi złożoność nlogk. ktoś da mniej?( ͡° ͜ʖ ͡°)
- Najlepsze
- Wszystkie komentarze
Przecież pomysł z kopcem Fibonacciego to jest praktycznie to samo, co napisał @wytrzzeszcz, tylko dużo bardziej skomplikowanie. Najzwyklejszy kopiec binarny będzie miał taką samą złożoność, dużo niższą stałą i da się to zakodzić w kilkunastu linijkach.
-wstawienie to O(1)
-znalezienie min to O(1)
-usuniecie minimum to O(logn)
Więc dla k liczb to klogn
https://www.cs.princeton.edu/~wayne/teaching/fibonacci-heap.pdf
I znalazłeś "lepszy" algorytm? :)
Ps.
Na szybko naturalnie też zaimplementowałbym to jako nlogk i nie próbował znajdywać czegoś lepszego, bo czasu by zabrakło.
@wytrzzeszcz: @snejdan
Dla "zabawy" dziś sobie zaimplementowałem to zadanko, z tą różnicą, że u mnie jest poszukiwanie najmniejszych k elementów z tablicy (a nie największych k elementów).
Może ktoś kiedyś jeszcze wpadnie na ten wątek i może przyda mu się kawałek kodu to zadanie rozwiązujące.
Naturalnie wszelkie komentarze do