Algorytmy i struktury danych · Middle · Pytanie 3 z 75
Jaki jest najgorszy przypadek quicksorta i kiedy występuje?
- ✓Poprawna odpowiedź: O(n²), gdy elementy osiowe ciągle dzielą tablicę bardzo nierówno
- 2O(n log n), gdy tablica zawiera wiele duplikatów
- 3O(n), gdy dane są już posortowane
Wyjaśnienie
Jeśli element osiowy jest zawsze najmniejszy lub największy (np. pierwszy element posortowanej tablicy), każdy podział odcina tylko jeden element. Losowy element osiowy lub mediana z trzech sprawiają, że jest to mało prawdopodobne; średnio O(n log n).