dfs 시간복잡도 질문

Question

안녕하세요 큰돌님, 강의 잘 듣고 있습니다. 간선리스트로 구현된 그래프에 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) 인가요?

큰돌 · Answer

안녕하세요 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점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.

인프런 AI 인턴 · Answer

안녕하세요, 인프런 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|)로 표현됩니다.