Computational complexity of STL algorithms and container methods
English
Gevorderd
In order to use STL correctly, you need to understand the computational complexity of STL algorithms and methods of STL containers. Besides, questions about computational complexity are often asked on job interviews. To pass this test you need to know: STL algorithms and data structures; what is big O notation (asymptotic notation) and what is O(1), O(n) and O(n*log (n)); what's the difference between average and worst case complexity. Next, we will assume that by default we are talking about STL containers consisting of n elements (container.size () == n) and only about computational complexity (time complexity). Any additional information will be explicitly mentioned in the question.
Beschrijving
Labels
35
Vragen
1 min
Per vraag
2:51
Gemiddelde tijd
4,2
Wedstrijdscore
13
Deelnemers
1. Educational explanations. 👍 Explanations cover why the correct answers are correct.
E.g.: #q1, #q2, #q3 etc.
2. Step-by-step approach to teaching. 👍
```
What's the complexity of std::nth_element(first, nth, last), where last - first = n and nth - first = m?
```
The question suggests that the complexity is O(m) but that is not true because you cannot find the minimal element in an array with O(1) complexity. nth_element always works O(n) on average https://en.cppreference.com/w/cpp/algorithm/nth_element
What's the complexity of std::set_intersect for two sorted ranges of n and m elements?
Options O(max(n, m)) and O(n+m) are equal (because (n+m)/max(n, m)<=2), so they are both correct.