Aktywne Wpisy
vorky +51
Treść przeznaczona dla osób powyżej 18 roku życia...
labelle +9
Moi rodzice całe życie prowadzili gospodarstwo rolne i praktycznie nigdzie nie jeździli. Nigdy nie widzieli morza ani gór, nie byli też za granicą. Wcześniej nie mieli takiej możliwości, a później, gdy już mogłam ich gdzieś zabrać, opiekowali się leżącą babcią. Babcia zmarła dwa miesiące temu i myślałam, że wreszcie po tylu latach będą mogli choć na chwilę odetchnąć i gdzieś wyjechać.
Mama bardzo chce, natomiast problemem jest tata. Nigdy nigdzie nie był i
Mama bardzo chce, natomiast problemem jest tata. Nigdy nigdzie nie był i
Aktywne Znaleziska
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?( ͡° ͜ʖ ͡°)
-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
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.
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