해당 문제를 set을 사용해서 풀었는데 이분탐색보다 속도가 느린 이유가 궁금합니다

std::set은 레드블렉 트리로 구현하여 삽입, 삭제, 검색 모두 O(logN)인걸로 알고있습니다. 이분 탐색도 시간 복잡도가 O(logN)인데 왜 std::set을 사용하면 더 느린지 궁금합니다.

아래는 풀이 소스코드입니다.

#include <bits/stdc++.h>

using namespace std;

int32_t t, n, m, tmp;
set<int32_t> s;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin >> t;

  while (t--) {
    cin >> n;
    s.clear();

    for (int32_t i = 0; i < n; ++i) {
      cin >> tmp;
      s.emplace(tmp);
    }

    cin >> m;

    for (int32_t i = 0; i < m; ++i) {
      cin >> tmp;

      if (s.contains(tmp)) {
        cout << "1\n";
      } else {
        cout << "0\n";
      }
    }
  }

  return 0;
}

답변 1

0

큰돌

2024-11-20T05:01:17.553Z

안녕하세요 누구게님 ㅎㅎ

먼저 해당 코드 제출하면 컴파일에러가 뜹니다.

 

이 이유는 contains를 사용하려면 C++20이여야 하는데 백준에서는 C++17까지만 제공되기 때문입니다. 이 때문에 set - find를 사용해야 하며 그럴 경우 1784ms 정도의 시간이 뜹니다.

 

std::set은 레드블렉 트리로 구현하여 삽입, 삭제, 검색 모두 O(logN)인걸로 알고있습니다. 이분 탐색도 시간 복잡도가 O(logN)인데 왜 std::set을 사용하면 더 느린지 궁금합니다.

-> 음.. 혹시 벤치마킹을 했을 때 차이가 나타난다는 말씀이신가요? 벤치마킹하신 링크 부탁드립니다.

---

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

누구게

2024-11-20T05:27:58.204Z

STL set 구조체활용(1) - 사용법(set은 만능이다?)
해당 글에 따르면 std::set은 레드 블랙트리를 사용하여 구현하였으며 삽입, 삭제, 검색 모두 O(logN)의 시간 복잡도를 가진다 라고 적혀있습니다.

std::set을 사용하면 단순 이분탐색보다 시간이 오래 걸리는 이유는 레드 블랙 트리 자료구조에서 오는 오버헤드 때문인건가요?

0

큰돌

2024-11-20T08:27:55.419Z

std::set을 사용하면 단순 이분탐색보다 시간이 오래 걸리는 이유는 레드 블랙 트리 자료구조에서 오는 오버헤드 때문인건가요?
-> 이걸 물어보는 것의 전제는 단순 이분탐색보다 시간이 오래걸린다.라는 건데 이렇게 생각하시는 이유나 어떤 케이스가 있으신가요? 좀 더 구체적으로 질문 부탁드립니다.

 

감사합니다.