-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
2776 암기왕 문제 시간복잡도에 관해 질문이 있습니다
24.04.22 22:17 작성 조회수 48
0
안녕하세요 큰돌님
암기왕 문제를 map을 사용한 경우 탐색에 log(n)의 시간복잡도를 갖는데, 이분탐색을 사용한 방법과 시간차이가 커서 질문드립니다.
sort를 사용하는 경우에 정렬에 nlog(n), 값을 찾는데 log(n)이 걸리며,
map을 사용하면 삽입에 n * log(n), 값을 찾는데 log(n)이 걸리니 결국 비슷할거라 생각했는데 시간차이가 2배나 나는 이유를 모르겠습니다 ㅜ
#include<bits/stdc++.h>
using namespace std;
int t, n, m, temp;
int main(){
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
cin >> t;
for(int i = 0; i < t; i++){
map<int, int> mp;
cin >> n;
for(int j = 0; j < n; j++){
cin >> temp;
mp.insert({temp, 0});
}
cin >> m;
for(int j = 0; j < m; j++){
cin >> temp;
if(mp.find(temp) == mp.end()) cout << 0 << '\n';
else cout << 1 << '\n';
}
}
return 0;
}
답변을 작성해보세요.
1
큰돌
지식공유자2024.04.24
안녕하세요 ㅎㅎ
sort를 사용하는 경우에 정렬에 nlog(n) + log(n) 맞습니다.
map
>>
삽입에 n * log(n), 값을 찾는데 log(n)
맞습니다. 시간복잡도는 둘 다 유사합니다.
2배차이
>>
2배 차이가 나는 것은 아마 이 문제에서만 그럴 수도 있고 확실히 이게 무조건 2배차이다. 라고 말씀드리기는 어렵습니다.
왜냐면 내부적으로 sort()와 map : 레드블랙트리에서 균형잡히게 정렬하는 시간을 비교해야하고 이 부분을 비교하기는 어렵고 단순 시간복잡도로는 유사하다는 것밖에 알 수 없습니다.
다만... 제가 수강생님을 위해 벤치마킹을 해봤는데요 ㅎㅎ
한 5배이상 차이나는 것을 볼 수 있습니다.
테스트코드.
#include <bits/stdc++.h>
using namespace std;
void A(){
vector<int> v;
for(int i = 50; i >= 1; i--){
v.push_back(i);
}
sort(v.begin(), v.end());
}
void B(){
vector<int> v;
map<int, int> mp;
for(int i = 50; i >= 1; i--){
v.push_back(i);
mp.insert({i, 0});
}
}
void test_latency(size_t iteration) {
PROFILE_START("A");
A();
PROFILE_STOP("A");
PROFILE_START("B");
B();
PROFILE_STOP("B");
}
int main() {
const size_t warmups = 1000;
const size_t tests = 100;
PROFILE_RUN_ALL(warmups, tests,
test_latency(__loop);
);
return 0;
}테스트 사이트. (sort가 더 좋게 나옵니다.)
이걸로는 확정지을 수는 없지만 한번에 sort 가 더 좋을 수도 있을 것 같습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
감사합니다.
답변 1