Algorytmy i struktury danych · Senior · Pytanie 68 z 75
Co daje quicksortowi losowość?
- 1Stabilność dla elementów z równymi kluczami
- ✓Poprawna odpowiedź: Oczekiwane O(n log n) dla każdych danych
- 3Gwarantowane O(n log n) w najgorszym przypadku
Wyjaśnienie
Przy losowym elemencie osiowym żadne ustalone dane nie są konsekwentnie złe, więc oczekiwanie obowiązuje dla każdych danych, także złośliwych. Najgorszy przypadek nadal jest możliwy, tylko skrajnie mało prawdopodobny.