인프런 커뮤니티 질문&답변
작성한 질문수
인구 이동 문제 시간복잡도 질문
작성
·
369
0
안녕하세요 강사님.
인구 이동 문제 시간복잡도에 대해서 질문드립니다.
N이 최대 50으로 모든 나라를 탐색한다고 가정하면 2500.
인구이동의 횟수는 최대 2000.
연결 컴포넌트를 구해야하기 때문에 방문 처리를 해주므로,
시간복잡도가 2500 * 2000으로 생각했습니다.
맞을까요?
답변 1
0
안녕하세요 재윤님 ㅎㅎ
네 맞습니다. 정확합니다. 다음 코드 처럼 되는거니까요.
// 2000
while(true){
bool flag =0;
fill(&visited[0][0], &visited[0][0] + 54 * 54, 0);
// 50 * 50
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){다만 2500부분이요. 최악의 경우의 수를 생각해 볼 필요는 있습니다.
자 이중 for문으로 2500번 순회합니다. 이 때 dfs가 작동이 되죠? 최악의 경우의 수 : dfs로 처음에 모든 정점을 간다고 하고 그 다음부터는 visited로 색칠되어 if문에 안걸린다고 해볼게요.
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(!visited[i][j]){그렇게 되면
2500 + 1 + 1 + ...... 가 되어
2500 + 1 * 2499 가 되겠죠?
즉, 약 5000이 됩니다.
아무리 if문으로 걸러서 dfs가 작동이 안된다고 한들. 해당 부분의 로직은 계산에 들어가게 됩니다.
시간복잡도를 따질 때 if continue를 해도 시간복잡도 계산에 들어가는 것을 알려드리기 위해 말씀을 드려봤습니다.
또 질문이 있으시다면 언제든지 질문 부탁드립니다.
또한 강의가 맘에 드셨다면 좋은 수강평과 별점 5점 꾹 부탁드립니다. 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
안녕하세요 샌디님 ㅎㅎ
해도 됩니다만 계산하기가 좀 껄끄러워서 빼는게 좋다고 생각합니다.
만약 v가 최악의 경우 2500이 되는데 이 경우에는 단한번 for문 돌리고 -> 종료되는 거라 그 때는 -> dfs자체도 많이 안돌게 되서 -> 전체적인 시간복잡도는 감소하게 되는 것이라서 최악이 어떤 경우인지를 파악하기가 어렵습니다.
감사합니다.
안녕하세요 큰돌님!
시간복잡도 관련 비슷한 질문이 이미 있어서 답글로 질문 드립니다!
dfs실행 이후에 for(pair<int,int> b: v) 부분은 시간 복잡도 계산에 포함이 안되는 건가요??
감사합니다!