인접행렬과 인접리스트 시간 차이

인접행렬과 인접리스트의 차이는 메모리 사용량에서 극명히 차이가 난다

다익스트라에서 두 자료구조를 사용했을 때 탐색 시간에서 차이가 날 것 같지만 몇 문제를 풀어봤을 때는 크게 나지 않았다

 

그 이유는 인접행렬은 간선의 개수와 상관없이 V^2만큼 탐색을 해버린다

하지만 인접리스트는 간선의 개수에 맞춰서 E개만큼 탐색을 한다

 

아마 V^2과 E개가 동등했다면 그 문제에서는 시간 차이가 나지 않을 것이다

 

[종만북 출처]

간선의 수가 V^2에 비해 훨씬 적은 그래프를 희소 그래프라고 부른다. 반대로 간선의 수가 V^2에 거의 비례하는 그래프를 밀집 그래프라고 한다. 희소 그래프에서는 인접 리스트를, 밀집 그래프에서는 인접 행렬을 사용하는 것이 더 유리하다. 그래프의 어떤 표현 방식을 사용하느냐에 따라 시간 복잡도는 달라진다