[CS] DFS, BFS의 O(V+E)에 대한 이해
2023. 8. 20. 13:02ㆍCS
인접리스트를 이용해 구현시 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가 적은 예외 상황이 있기 때문이고 이를 처리해주기 위함이다.
'CS' 카테고리의 다른 글
[CS][X] 프림 알고리즘 시간 복잡도에 대한 이해 (0) | 2023.08.20 |
---|---|
[CS] 크루스칼 알고리즘 시간 복잡도에 대한 이해 (0) | 2023.08.20 |
[CS] Red-Black Tree (0) | 2023.08.17 |
[CS] 최대최소힙 (0) | 2023.08.12 |
[CS] Array와 Linked List의 차이 (0) | 2023.08.11 |