Algorytmy i struktury danych · Senior · Pytanie 58 z 75
Dlaczego głębokość rekurencji quicksorta jest problemem i jak się ją ogranicza?
- ✓Poprawna odpowiedź: Złe elementy osiowe dają głębokość n; rekurencja idzie do mniejszej części
- 2Głęboka rekurencja czyni sortowanie niestabilnym dla równych kluczy
- 3Głębokość to zawsze log n, więc problemu nie ma
Wyjaśnienie
Rekurencja do mniejszej części i pętla po większej gwarantują głębokość stosu O(log n), nawet gdy czas się degraduje. Introsort również ogranicza głębokość i przechodzi na heapsort.