컴퓨터 사이언스/Algorithm
DFS와 BFS에서 인접행렬 vs 인접리스트
kimjingyu
2023. 7. 23. 22:00
728x90
시간복잡도
- 인접행렬: O(V^2)
- 인접리스트: O(V + E) == O(max(V,E))
- 정점의 개수와 간선의 개수 중 더 큰 값을 기준으로
- 인접리스트는 간선의 개수가 적을수록 메모리 공간을 덜 잡아먹는 장점이 있었음
- 만약 간선의 개수가 V에 비해 월등히 적으면 O(V)로 표현이 될 수 있음
- 즉, 간선 개수가 적으면 인접리스트가 훨씬 유리해진다.
728x90