История изменений

Ещё одно доказательство, что ИИ уже умней людей.

In the worst case, the loop can perform up to n erasures (where n is the size of the vector). Each erase on a std::vector is O(n) in the worst case because all subsequent elements must be shifted. Consequently, the overall time complexity is O(n^2).

Ещё одно доказательство, что ИИ уже умней людей.

The dominant cost here comes from calling vector::erase(it) in a loop. Each erase at position it must shift all subsequent elements down by one, which is an O(m) operation where m is the number of elements after it. In the worst case you erase Θ(n) times (e.g. if half the elements are odd), and each erase on average shifts Θ(n) elements, giving:

• First loop: – Up to ≈n/2 calls to erase × O(n) per call ⇒ O(n²) in the worst case – Plus the O(n) cost of advancing the iterator when you don’t erase
• Second loop (printing): O(n)

Putting it all together, the overall time complexity is O(n²) (worst-case).

Note: If you need to remove elements by predicate in linear time, you can use the “erase–remove” idiom:

a.erase(
    std::remove_if(a.begin(), a.end(), [](int x){ return x % 2 != 0; }),
    a.end()
);

which runs in two passes over the data (O(n)) and then a single O(1) range‐erase of the tail.