Выбор ответа Junior Алгоритмы STL и ranges спрашивают часто обновлено
Сложность std::sort
Вопрос
Какую сложность гарантирует std::sort с C++11?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(n log n) сравнений в худшем случае. С C++11 стандарт требует O(n log n) сравнений и в худшем случае.
Варианты ответа
- O(n log n) в среднем, но O(n²) в худшем
- O(n) для целых чисел через поразрядную
- O(n log n) сравнений в худшем случаеправильный ответ
- O(n²) сравнений в худшем случае
Разбор
С C++11 стандарт требует O(n log n) сравнений и в худшем случае. Реализации используют introsort: быстрая сортировка с переключением на пирамидальную при слишком глубокой рекурсии.
- O(n²) в худшем было у чистого quicksort и допускалось до C++11.
- Поразрядной сортировки в
std::sortнет, он работает только через сравнения.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.