6
std :: set에서 여러 요소를 지우는 복잡성을 파악하려고합니다. 나는 소스로 this page을 사용하고 있습니다.std :: set simplise complexity anomality?
반복기를 사용하여 단일 항목을 지우는 복잡성은 O (1)으로 상각되지만 범위 형식을 사용하여 여러 항목을 지우는 것이 log (c.size()) + std :: distance (first, last) (즉, 세트의 크기의 로그 + 삭제 된 요소의 수).
지우는 요소의 수 (n)가 집합의 요소 수 (m)보다 훨씬 적은 경우 지우는 요소를 반복하고 그 중 하나를 지우는 것이 n < < m으로 가정하면 하나의 호출 (O (log m))으로 지우는 것보다 시간이 더 빠릅니다 (O (n)).
분명히, 실제로 두 번째 형식의 내부 구현은 위의 루프를 수행합니다.
사이트에서 오류가 발생 했습니까? 사양의 버그? 방금 뭔가 빠졌나요?
덕분에, Shachar
로그입니다 (c.size()) + 표준 : 거리 (첫 번째, 마지막) (예 - 세트의 크기 + 삭제 된 요소의 수의 로그). _ - 고정 세트의 크기는 O (n)과 정확히 동일합니다. 여기서 n은 삭제 된 요소의 수이며, 하나씩 삭제하면됩니다. – Cthulhu
흥미로운 점은 차이점을 확인하기 위해 두 가지 방법으로 테스트 할 수 있었다고 생각합니다. 어쩌면 각 개별 지우기 후에 반복기를 다시 설정하는 데 약간의 오버 헤드가 생길 수 있습니다 (반복자가 무효화되는 것 같음) –
@Cthulhu, 복잡성에 더하기가 사용될 때마다 동일한 논리가 적용됩니다. 상수 (또는 심지어 한정)로 가정하는 모든 것은 자동으로 O (1)의 복잡성을 갖습니다. –