Algorytmy i struktury danych · Senior · Pytanie 30 z 75
Dlaczego algorytm O(n log n) może przegrać z O(n²) na prawdziwych danych?
- ✓Poprawna odpowiedź: Big O ukrywa stałe, a dla małych n to one dominują
- 2Algorytmy O(n²) są kompilowane z większymi optymalizacjami
- 3O(n log n) obowiązuje tylko, gdy n jest potęgą dwójki
Wyjaśnienie
Sortowanie przez wstawianie wygrywa ze scalaniem poniżej kilkudziesięciu elementów dzięki znikomemu narzutowi i przyjaznemu dla cache dostępowi. Dlatego Timsort i introsort przełączają się na wstawianie dla małych serii.