map.find() 시간 복잡도

Question

나는지도가있는 경우 :

map myMap<string,vector<int>> 

최고, 평균, 그리고 최악의 경우 시간 복잡도는 키를 발견 한 다음를 찾기 위해 벡터를 반복하는 것입니다 무엇 특정 int?

map.find() 메서드는 O (log n)입니다. 그러나 벡터 내에서 int를 검색해야한다는 사실은 시간 복잡성을 변경합니까?

감사합니다.

Answer 1

이것이 C++라고 말하면 도움이됩니다. std :: map은 일반적으로 이진 트리로 구현되므로 find 연산에서 O (log (n))가 발생합니다.

O (log (n) + m)입니다. 여기서 n은 맵의 크기이고 m은 (각) 벡터의 크기입니다. 한 번만 조회 한 다음 키에 해당하는 전체 벡터를 반복한다고 가정합니다.

매우 작은 벡터가 없으면 log (n)이 천천히 커지기 때문에 log (n)은 <m이되어야합니다. 따라서 알고리즘은 O (m)이어야합니다.