C++ 시간복잡도 질문입니다.

#include<vector>
#include<map>
#include<iostream>>

using Room = unsigned int;

struct User {
    int number_;
public:
    User(int number):number_(number) {}
};
std::map<Room, std::vector<User*>> map;

bool SearchUser(Room room, int userNumber) {
    //룸을 찾고( logN)
    auto findIter = map.find(room);

    if (findIter != map.end()) {
        //해당 룸에 유저 찾기 (N)
        for (auto iter = findIter->second.begin(); iter != findIter->second.end(); ++iter) {

            if ((*iter)->number_ == userNumber) {
                return true;
            }
        }
    }

    return false;
}

int main() {

    //Room에 User 삽입
    map[0].emplace_back(new User(1));
    map[0].emplace_back(new User(2));

    map[1].emplace_back(new User(3));
    map[1].emplace_back(new User(4));

    map[3].emplace_back(new User(5));
    map[3].emplace_back(new User(6));

    std::cout << std::boolalpha<< SearchUser(0, 2) << "\n";

}

여기서 SearchUser의 시간 복잡도가 어떻게 되나요?

map에서 찾는 데 logn 이 걸리고 다시 n 만큼 반복문을 돌아서 최종적으로 user를 찾습니다.
추측만 하고 있어서 정확하게 알고 싶어서 질문드립니다.

감사합니다.

안녕하세요. map을 탐색하는데는 logN이 걸리는건 맞습니다만, logN이 걸려서 찾은 룸 안의 사람수가 N에 비례하는건 아닌거같네요.

N은 입력의 크기를 말하니, User숫자일텐데요.
하나의 룸안에 있는 User의 숫자가 입력크기에 비례하지 않으면 그 복잡도를 N으로 볼 수 없습니다.

답변 감사합니다 :+1: