Jaka jest złożoność set_intersection w C++?

Question

Jaka jest złożoność następującego kodu?

set<int> S1, S2, ans; 
set_intersection(S1.begin(), S1.end(), S2.begin(), S2.end(), inserter(ans, ans.begin())) 

gdzie S1 i S2 kilka zestawów non_empty i ans jest zbiorem pustym.

Wiem, że wstawienie posortowanego zakresu do zestawu jest liniowe; ale wstawia za pomocą liniowego insertera?

Answer 1

Wprowadzający zapamiętuje miejsce ostatniego wstawienia każdego przedmiotu i próbuje wstawić następny element w tym samym miejscu. To jest O (1), jeśli jest to właściwe miejsce.

Co oznacza, że ​​skopiowanie posortowanego zakresu do insertera jest ogólnie liniowe, więc jesteś tutaj dobry.