Выбор ответа Junior Сложность спрашивают часто обновлено
Сложность сортировки
Вопрос
Какую сложность по времени ждать от arr.sort((a, b) => a - b) в современных движках?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(n log n). V8 (Chrome, Node.js) использует TimSort, он O(n log n) в худшем случае и стабилен (стабильность требует спецификация с ES2019).
Варианты ответа
- O(n)
- O(n log n)правильный ответ
- O(n²) всегда
- O(log n)
Разбор
V8 (Chrome, Node.js) использует TimSort, он O(n log n) в худшем случае и стабилен (стабильность требует спецификация с ES2019). Это стандартная оценка, на которую опираются в задачах.
- O(n): сортировка сравнениями быстрее n log n не бывает.
- O(n²): так у пузырька и вставок, а не у встроенной сортировки.
- O(log n): даже прочитать массив стоит O(n).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.