dfs 시간복잡도 질문
안녕하세요 큰돌님, 강의 잘 듣고 있습니다.
간선리스트로 구현된 그래프에 dfs를 적용할 경우,
시간복잡도는 O(|V|+|E|)로 알고 있습니다.
만약, 주어진 그래프에서 각 노드가 4방향으로 간선이 뻗어있을 경우, 아래와 같은 방식으로 탐색을 이어나갑니다.
int mv[4][2]={{0,1},{0,-1},{1,0},{-1,0}}
for(int i=0; i<4; i++;)
{
int ny = y+mv[i][0]
int nx = x+mv[i][1]
}이때, 노드 개수를 V개면, 간선의 개수는 각 노드 별로 4개니까, |E|=|V|*4로 계산해서, 시간복잡도는 O(|V|*5) 인가요?
답변 2
0
안녕하세요 lego님 ㅎㅎ
이때, 노드 개수를 V개면, 간선의 개수는 각 노드 별로 4개니까, |E|=|V|*4로 계산해서, 시간복잡도는 O(|V|*5) 인가요?
>> 음.. 저거 4방향이 아마 이런 그림 아닐까요?
실제 간선의 수 |E|는 대략 |V|가 되서 (|V|+|V|) 즉, O(2|V|)가 될 것입니다.
근데 만약 해당 4방향 간선이 겹치지 않고 유니크하다면 lego님 말씀처럼 |E|=|V|*4로 계산해서, 시간복잡도는 O(|V|*5)가 맞습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다.
lego0313님, 질문 주셔서 감사합니다.
그래프에서 DFS(깊이 우선 탐색)의 시간 복잡도를 계산할 때는 모든 정점과 간선을 탐색하는 경우를 기준으로 합니다. 즉, O(|V|+|E|)가 되는 것이 일반적입니다.
말씀하신 경우에는 각 정점에서 4방향의 간선으로 연결된 그래프를 가정하신 것 같습니다. 이 경우 모든 정점에 대해 4개의 간선이 있다고 가정하면, 각 정점당 간선이 2번씩 계산되므로 (무향 그래프라면 한 간선을 두 정점이 공유하기 때문에) 실제 간선의 수 |E|는 대략 |V|*2 가 됩니다. 따라서, 정확한 시간 복잡도는 O(|V|+2|V|) 즉, O(3|V|)가 될 것입니다.
그러나 이러한 계산은 그래프가 밀집되어 있거나 완전 그래프인 특수한 경우에 한합니다. 실제로는 간선의 수가 정점의 수와는 독립적으로 그래프에 따라 다르기 때문에 일반적으로 시간 복잡도를 O(|V|+|E|)로 표현합니다.
결론적으로, 주어진 그래프에서 각 노드가 4방향으로 간선이 있다고 가정하더라도 각 간선을 두 노드가 공유한다는 점을 고려하면, 시간 복잡도는 O(3|V|)이 될 수 있지만, 이것은 그래프의 특성을 감안한 특수한 경우의 계산이며, 일반적인 경우에는 여전히 O(|V|+|E|)로 표현됩니다.
코살구 1주차 1940번 문제 조건과 프라이빗 테스트 불일치 문의
0
13
2
문제를 고민하는 시간 관련
0
21
2
코딩살구클럽
0
32
2
코딩살구클럽 문의
0
32
2
코딩살구클럽 승인
0
34
2
DP 경우의 수 설명이 이해가 되지 않습니다.
0
33
2
3-F 채점 관련 질문
0
30
1
BFS, DFS 활용이 되는 상황에서의 방향성
0
32
2
코딩살구클럽 승인
0
44
2
코딩살구클럽승인
0
39
3
코딩살구클럽 승인
0
51
2
3-D 관련 질문
0
35
2
코살구 회원가입 문의
0
45
2
코살구 로그인 문제
0
65
2
3-A 문제 풀이 관련 질문
0
56
3
2-O 질문 있습니다
0
38
2
2-T 문제에 관한 질문
0
40
2
코딩 살구 클럽 접속 및 사용방법 문의
0
63
2
안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~
0
67
2
코딩살구클럽 로그인문제
0
85
3
코딩 살구 클럽 로그인 문제
0
85
2
2-J 채점관련 질문
0
67
3
코딩 살구 클럽 Python 지원 가능 여부
0
77
1
살구클럽 아이디 없음 문제
0
76
1