[CS] DFS, BFS의 O(V+E)에 대한 이해

인접리스트를 이용해 구현시 DFS, BFS 모두 O(V+E)의 시간복잡도를 가진다.

이는 다음과 같이 이해해볼 수 있다.

 

V가 1억개 있고 E는 0 즉 간선이 하나도 없다고 생각해보자. 그러면 탐색하기 위해서는 V를 모두 돌며 결국 하나도 연결되지 않았다는 것을 알아야 할 것이다. 그래서 이 경우에는 O(V)가 될 것이다.

이번에는 V가 1억개 있고 서로 모두 연결 되어 있다고 생각해보자. 그러면 모든 간선에 대해서 확인하는 절차(이 노드가 이미 방문했던 노드라도 바로 그걸 '확인'해야 한다)가 들어가기 때문에 간선의 개수는 O(V+E)가 된다. 그런데 여기서 E는 V * (V-1)이므로 O(V)보다 훨씬 크게 된다. 그래서 O(E)가 된다.

 

결국 O(V+E)가 의미하는 것은 간선이 연결되어 있는 상황에 따라 O(V)와 O(E) 중 둘 중 더 큰 값이 되게 된다는 것을 의미한다. 

O(V) <= O(E) <= O(V+E)라고 보면 될듯하다. O(V)가 있는 이유는 V보다 E가 적은 예외 상황이 있기 때문이고 이를 처리해주기 위함이다.