Algorytmymedium

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

Tagi

#quickselect#selection#partition#big-o

Odpowiedź

Quickselect służy do znalezienia k‑tego elementu (np. mediany) bez pełnego sortowania tablicy. Używa partycjonowania jak quicksort i ma oczekiwane O(n), ale w najgorszym przypadku może spaść do O(n^2).

Powiązane pytania

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

Algorytmy

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

#quickselect#partition#selection