Algorytmymedium

Co to jest Quickselect i jaka jest jego średnia złożoność czasowa?

Tagi

#quickselect#partition#selection#big-o

Odpowiedź

Quickselect znajduje k-ty najmniejszy element przez partycjonowanie jak QuickSort, ale schodzi rekurencyjnie tylko w jedną stronę. Średnio działa w O(n), a w najgorszym przypadku O(n²) (złe pivoty).

Powiązane pytania

Algorytmy

Quickselect: do czego służy i jaka jest jego oczekiwana złożoność?

#quickselect#selection#partition

Algorytmy

Co to jest kolejka monotoniczna i jak daje max w oknie w O(n)?

#deque#monotonic-queue#sliding-window

Algorytmy

Counting sort: kiedy może być szybszy niż sortowanie O(n log n)?

#counting-sort#sorting#stability

Algorytmy

Kruskal vs Prim dla MST — czym się różnią?

#mst#kruskal#prim

Algorytmy

Losowy pivot w QuickSort/Quickselect — czemu pomaga?

#randomization#quicksort#quickselect

Algorytmy

Co to jest monotonic stack i jakie problemy rozwiązuje?

#stack#monotonic-stack#next-greater