Treść pytania:
Które określenie najlepiej opisuje złożoność obliczeniową algorytmu quicksort?
Odpowiedzi:
- Jest zawsze niższa niż złożoność każdego innego algorytmu sortowania.
- Jest wyższa niż złożoność sortowania bąbelkowego.
- Jest wyższa niż O(n2)
- Jest różna w zależności od wyboru elementu rozdzielającego.
Poprawna odpowiedź: Jest różna w zależności od wyboru elementu rozdzielającego.
Uzasadnienie: Złożoność algorytmu quicksort zależy od wyboru elementu podziałowego (pivotu). W najlepszym przypadku (gdy pivot dzieli tablicę na dwie równe części), złożoność wynosi O(nlogn). W najgorszym przypadku (gdy pivot jest zawsze największy lub najmniejszy), złożoność wynosi O(n2).
