[wytrzzeszcz]

#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?( ͡° ͜ʖ ͡°)

[P.....k]

@wytrzzeszcz: Randomized quick sort

[wytrzzeszcz]

@Poranekk: ale masz nlogn (chociaż niezłe) to nadal dla n>>k, nlogn > nlogk

[P.....k]

@wytrzzeszcz: fakt, słabo łącze fakty o tej godzinie. Chyba nic więcej nie przychodzi mi do głowy. Powodzenia w szukaniu programirku!

[snejdan]

@wytrzzeszcz: fibonacci heap klogn
-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

[wytrzzeszcz]

@Poranekk: raczej chciałem by ogólnie mirki ruszyły szare komórki bo ktoś tam się spinał że sortowania w robocie nigdy nie napiszesz

[wytrzzeszcz]

@snejdan: ale musisz mieć posortowany zbiór duży na n by klogk śmigło. ale przyznam niezłe nezłe

[wytrzzeszcz]

@snejdan: dobra jestem bucem łap pluse

[D.....n]

@snejdan: @wytrzzeszcz:
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.

[Adaslaw]

no i wyszła mi złożoność nlogk

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.

[Adaslaw]

Zadanie wybierz k największych elementów z pośród n. gdzie n>>k

@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