C++ set_intersection'ın karmaşıklığı nedir?

Question

Aşağıdaki kodun karmaşıklığı nedir?

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

nerede S1 ve S2 bazı non_empty setleri ve ans boş kümesidir.

Bir kümeye sıralanmış bir aralığın eklenmesinin doğrusal olduğunu biliyorum; ama aynı zamanda yerleştirici kullanarak ekleme mi?

Answer 1

Yerleştirici, her bir öğeyi en son nereye eklediğini hatırlar ve bir sonraki öğeyi aynı yere yerleştirmeyi dener. Bu doğru yer ise O (1).

Bu, yerleştiriciye sıralanmış bir aralığın kopyalanması genel olarak doğrusal olduğu anlamına gelir;