ID: 2687
Algorytmy
Średnie
Źródło: Arkusze CKE
Jakie sformułowanie najlepiej oddaje złożoność obliczeniową algorytmu quicksort?
Warianty odpowiedzi
-
A
jest większa niż O(n2)
-
B
jest większa niż złożoność sortowania bąbelkowego
-
C
jest zawsze mniejsza niż złożoność jakiegokolwiek innego algorytmu sortowania
-
D
jest różna w zależności od wyboru elementu dzielącego
Wyjaśnienie
Algorytm Quicksort opiera się na wyborze tzw. pivota, czyli elementu podziału, według którego dzieli całą tablicę na dwie mniejsze części.
Wydajność tego algorytmu wprost zależy od tego, jak trafnie zostanie wybrany pivot:
- Jeśli trafi w środek wartości, tablica dzieli się równo na pół, co daje świetną złożoność O(n log n).
- Jeśli wybór okaże się niefortunny (np. trafimy na element najmniejszy w posortowanej tablicy), podział będzie skrajnie nierówny i złożoność spadnie do O(n²).
Dlatego właściwa odpowiedź wskazuje, że złożoność jest różna i zależy bezpośrednio od wyboru elementu dzielącego.