Algorytmy i struktury danych · Senior · Pytanie 63 z 75
Jaka jest złożoność Array.prototype.sort w V8 na już posortowanej tablicy?
- ✓Poprawna odpowiedź: Około O(n)
- 2O(n log n) bez żadnych skrótów
- 3O(n²)
Wyjaśnienie
Timsort wykrywa, że cała tablica to jedna seria rosnąca, i robi tylko liniowe sprawdzenie. To jeden z powodów, by wybrać wbudowane sortowanie zamiast własnego quicksorta.