Вычислительная сложность STL алгоритмов и методов контейнеров
Русский
Advanced
Для того, чтобы правильно пользоваться STL, нужно разбираться в вычислительных сложностях STL-алгоритмов и методов STL-контейнеров. Кроме того, без подобных вопросов не проходит ни одно приличное собеседование на должность С++ разработчика. Для прохождения этого теста нужно знать: алгоритмы и структуры данных STL; что такое О-символика и что означают записи вида O(1), O(n), O(n*log(n)); что такое сложность в худшем случае и сложность в среднем (амортизированная сложность). Далее будем по умолчанию считать, что речь идёт о контейнерах, содержащих n элементов (container.size() == n) и только о вычислительной сложности (сложности по времени). О контейнерах другого размера в вопросе будет сказано явно.
Description
Tags
35
Questions
1 min
Per question
3:12
Average time
4.0
Contest Score
4.3
Community Rating
13
Participants
Educational explanations. 👍 Explanations cover why the correct answers are correct and why the wrong answers are wrong (when appropriate). E.g.: #q1, #q2, #q3, etc.
The original verdict was confirmed to be correct.
In addition to the above nominations:
Step-by-step approach to teaching. 👍 E.g.: #q1, #q9, #q15, etc.
И последний вопрос. Какова сложность в среднем функции std::nth_element, если применить её к интервалу длины n для поиска элемента, который после сортировки оказался бы на m-ой позиции интервала?
```
Ответ и объяснение предлагается быть O(m), что не является правдой. nth_element работает за линейное время по стандарту. Также невозможно найти минимальный элемент за константное количество сравнений. См https://en.cppreference.com/w/cpp/algorithm/nth_element 1,3)
Варианты ответа O(max(n, m)) и O(n+m) - одно и то же (так как отличаются не больше, чем в 2 раза), поэтому они оба правильные.