Fiszki do Sortowanie szybkie (quicksort)
Sortowanie Szybkie (Quicksort): Algorytm, Złożoność, Pivot
Dotknij, aby odwrócić · Przesuń, aby nawigować
Quicksort
29 fiszek
Fiszka 1
Pytanie: Jaka jest oczekiwana złożoność czasowa algorytmu Quicksort?
Odpowiedź: O(n log n), gdzie n to liczba elementów do posortowania.
Fiszka 2
Pytanie: Dlaczego Quicksort osiąga złożoność O(n log n) w przypadku średnim?
Odpowiedź: Ponieważ każde partycjonowanie wymaga liniowego czasu (O(n)), a liczba poziomów rekurencji wynosi log n dzięki efektywnemu dzieleniu problemu na pół.
Fiszka 3
Pytanie: Jaka jest złożoność czasowa Quicksortu w najgorszym przypadku?
Odpowiedź: O(n²).
Fiszka 4
Pytanie: Kiedy występuje najgorszy przypadek dla Quicksortu?
Odpowiedź: Gdy pivot konsekwentnie dzieli listę na bardzo nierówne części (np. zawsze jest to najmniejszy lub największy element), prowadząc do n poziomów rekure
Fiszka 5
Pytanie: Podaj przykład sytuacji, w której Quicksort osiąga złożoność O(n²) przy wyborze pierwszego lub ostatniego elementu jako pivota.
Odpowiedź: Sortowanie już posortowanej listy lub posortowanej w odwrotnej kolejności.
Fiszka 6
Pytanie: Jaki jest wpływ wyboru pivota na wydajność Quicksortu?
Odpowiedź: Ma ogromny wpływ, zwłaszcza w kontekście unikania najgorszego przypadku.
Fiszka 7
Pytanie: Jaka strategia wyboru pivota jest najprostsza, ale może prowadzić do O(n²) dla już posortowanych danych?
Odpowiedź: Wybór pierwszego/ostatniego elementu jako pivota.
Fiszka 8
Pytanie: Dlaczego wybór środkowego elementu jako pivota jest lepszy niż pierwszego/ostatniego, ale nadal podatny na specyficzne układy danych?
Odpowiedź: Jest lepszy, ale nadal może prowadzić do gorszej wydajności w przypadku specyficznych, niekorzystnych układów danych.
Fiszka 9
Pytanie: Która strategia wyboru pivota znacznie zmniejsza prawdopodobieństwo wystąpienia najgorszego przypadku w Quicksort?
Odpowiedź: Losowy pivot.
Fiszka 10
Pytanie: Na czym polega strategia wyboru pivota "mediana z trzech"?
Odpowiedź: Polega na wyborze mediany spośród trzech elementów (np. pierwszego, środkowego i ostatniego) podlisty.