Выбор ответа Middle Алгоритмы STL и ranges обновлено
Медиана без полной сортировки
Вопрос
Как быстрее всего найти медиану в векторе из миллиона чисел, если порядок остальных не важен?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: std::nthelement по позиции n / 2: в среднем O(n). nthelement (вариант quickselect) ставит на нужную позицию тот элемент, что был бы там после сортировки, в среднем за O(n), а слева и справа элементы разбиты, но не отсортированы. - std::sort это O(n log n), а не O(n). - partialsort до…
Варианты ответа
std::sortи взять середину: это O(n) для чиселstd::nth_elementпо позицииn / 2: в среднем O(n)правильный ответstd::partial_sortдо середины вектора: это O(n)- Через
std::max_elementв цикле по половине элементов
Разбор
nth_element (вариант quickselect) ставит на нужную позицию тот элемент, что был бы там после сортировки, в среднем за O(n), а слева и справа элементы разбиты, но не отсортированы.
std::sortэто O(n log n), а не O(n).partial_sortдо середины это O(n log n) и делает лишнюю работу.- Повторный поиск максимума это O(n²).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.